DP9 二項式系數 Binomial Coefficient @geeksforgeeks

Following are common definition of Binomial Coefficients.
1) A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n.

2) A binomial coefficient C(n, k) also gives the number of ways, disregarding order, that k objects can be chosen from among n objects; more formally, the number of k-element subsets (or k-combinations) of an n-element set.

The Problem
Write a function that takes two parameters n and k and returns the value of Binomial Coefficient C(n, k). For example, your function should return 6 for n = 4 and k = 2, and it should return 10 for n = 5 and k = 2.

1) Optimal Substructure
The value of C(n, k) can recursively calculated using following standard formula for Binomial Cofficients.

   C(n, k) = C(n-1, k-1) + C(n-1, k)
   C(n, 0) = C(n, n) = 1

2) Overlapping Subproblems
Following is simple recursive implementation that simply follows the recursive structure mentioned above.

package DP;

public class BionomialCoefficient {

	public static void main(String[] args) {
		int n = 5, k = 2;
		System.out.println(binomialCoeffRec(n, k));
		System.out.println(binomialCoeffDP_2D(n, k));
		System.out.println(binomialCoeffDP_1D(n, k));
	}

	public static int binomialCoeffRec(int n, int k){
		if(k==0 || k==n){
			return 1;
		}
		return binomialCoeffRec(n-1, k-1) + binomialCoeffRec(n-1, k);
	}
	
	// Returns value of Binomial Coefficient C(n, k)
	// Time Complexity: O(n*k), Auxiliary Space: O(n*k)
	public static int binomialCoeffDP_2D(int n, int k){
		int[][] dp = new int[n+1][k+1];
		
		// Caculate value of Binomial Coefficient in bottom up manner
		for(int i=0; i<=n; i++){
			for(int j=0; j<=Math.min(i, k); j++){
				if(j==0 || j==i){	// Base Cases
					dp[i][j] = 1;
				}else{	// Calculate value using previosly stored values
					dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
				}
			}
		}
		return dp[n][k];
	}
	
	// A space optimized Dynamic Programming Solution
	// Time Complexity: O(n*k), Auxiliary Space: O(k)
	public static int binomialCoeffDP_1D(int n, int k){
		int[] dp = new int[k+1];
		dp[0] = 1;
		
		for(int i=1; i<=n; i++){
			for(int j=Math.min(i, k); j>0; j--){	// 逆序
				dp[j] += dp[j-1];
			}
		}
		return dp[k];
	}
}