动态规划 计算二项式系数

动态规划计算二项式系数，主要用到了一个性质C（m，n）=C（m，n-1）+C(m-1，n-1)；

这个式子将C(m , n)的计算问题表述为了（问题描述）C(m-1 , n -1)和C(m -1,n)两个较小的交叠子问题。

初始条件：C(m , m) = C(n , 0) = 1

得到c（n,k）:

：

代码1（c（n，k）:k为固定值）：

代码2（求c(n,k):k=0……n）：

1. import java.util.Scanner;  
2.   
3. /** 
4.  *  
5.  * @author fool song 计算二项式系数 求出所有项 
6.  */  
7. public class BinoCoeff2 {  
8.     public static void main(String[] args) {  
9.         // C（n,m）  
10.         System.out.println("输入n：");  
11.         Scanner input = new Scanner(System.in);  
12.         int n = Integer.valueOf(input.nextInt());  
13.         getBinoCoeff(n);  
14.     }  
15.   
16.     public static void getBinoCoeff(int n) {  
17.         int[][] arr = new int[n + 1][n + 1];  
18.         for (int i = 0; i <= n; i++) {  
19.             for (int j = 0; j < i + 1; j++) {  
20.                 if (i == j || j == 0) {  
21.                     arr[i][j] = 1;  
22.                 } else {  
23.                     arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];  
24.                 }  
25.             }  
26.         }  
27.         printf(arr, n);  
28.     }  
29.   
30.     public static void printf(int[][] arr, int n) {  
31.         for (int i = 0; i < n + 1; i++) {  
32.             System.out.println("c("+n+","+i+")="+arr[n][i]);  
33.         }  
34.     }  
35. }