/**
 * Description of the class.
 *   @author Dave Reed
 *   @version 4/1/14
 *
 */
public class Binomial {
    
	/** 
	 * Calculates n choose k (using top-down recursion)
	 *   @param n the total number to choose from (n > 0)
	 *   @param k the number to choose (0 <= k <= n)
	 *   @return n choose k (the binomial coefficient)
	 */
	public static int binomialTopDown(int n, int k) {
    if (k == 0 || n == k) {
        return 1;
    }
    else {
        return binomialTopDown(n-1, k-1) + binomialTopDown(n-1, k);
    }
}
 
/** 
 * Calculates n choose k (using dynamic programming)
 *   @param n the total number to choose from (n > 0)
 *   @param k the number to choose (0 <= k <= n)
 *   @return n choose k (the binomial coefficient)
 */
 public static int binomialBottomUp(int n, int k) { 
    if (n < 2) {
        return 1;
    }
    else {
        int bin[][] = new int[n+1][n+1];        // CONSTRUCT A TABLE TO STORE

        for (int r = 0; r <= n; r++) {          // COMPUTED VALUES
            for (int c = 0; c <= r && c <= k; c++) {
                if (c == 0 || c == r) {
                    bin[r][c] = 1;              // ENTER 1 IF BASE CASE
                }
                else {                          // OTHERWISE, USE FORMULA
                    bin[r][c] = bin[r-1][c-1] + bin[r-1][c];
                }
            }
        }
        return bin[n][k];                       // ANSWER IS AT bin[n][k]
    }
}


    public static void main(String[] args) {
        System.out.println(binomialBottomUp(64, 8));
        System.out.println(binomialTopDown(64, 8));
    }
    
}