/**
 * Calculate binomial coefficient using top-down and bottom-up.
 *   @author Dave Reed
 *   @version 10/25/24
 */
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

			for (int r = 0; r <= n; r++) {
				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) {
		int n = 64;
		int k = 8;
		System.out.println(binomialBottomUp(n, k));
		System.out.println(binomialTopDown(n, k));
	}

}