/**
* 计算二项式系数 <br/>
* 动态规划
* O(nk)
*
* @author chenxuegui
*
*/
public class BinomialCoefficient
{
public static void main(String[] args)
{
int n = 4;
int k = 3;
System.out.println(binomial(new int[n+1][n+1], n, k));
}
/**
* 计算二项式系数
* @param recode
* @param n
* @param k
* @return
*/
public static int binomial(int[][] recode, int n, int k)
{
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= Math.min(k, i); j++)
{
if (j == i || j == 0)
{
recode[i][j] = 1;
}
else
{
recode[i][j] = recode[i - 1][j] + recode[i - 1][j - 1];
}
}
}
return recode[n][k];
}
}
动态规划——1 计算二项式系数