DP.rar_K.

package Algorithm; /** * @author wangyitao * i ：被划分的整数 * j ：划分中的最大值 */ public class DP { final static int N = 6; private static int a_123[][] = new int[N][N];//存储前三行处理的划分 private static int a_4[][] = new int[N][N];//存储第4行处理的划分 private static int a_5[][] = new int[N][N]; /** * a[i][j]中保存的是整数i的划分中最大值不超过j的划分的个数 * */ private static void partition_123(){ a_123[0][0] = 1; for(int i=0; i<N; i++) for(int j=1; j<N; j++){ if (i<j) { a_123[i][j] = a_123[i][i]; } else { a_123[i][j] = a_123[i][j-1] + a_123[i-j][j]; } } } private static void partition_4(){ a_4[0][0] = 1; for(int i=1; i<N; i++){ a_4[i][1] = 1; } for(int i=1; i<N; i+=2){ a_4[0][i] = 1; } for(int i=2; i<N; i++){ for(int j=3; j<N; j+=2){ if(j>i){ if(i%2 == 1){ a_4[i][j] = a_4[i][i]; } else { a_4[i][j] = a_4[i][i-1]; } } else { a_4[i][j] = a_4[i-j][j] + a_4[i][j-2]; } } } } private static void partition_5(){ for(int i=1; i<N; i++){ a_5[0][i] = 1; a_5[1][i] = 1; } for(int i=2; i<N; i++){ for(int j=1; j<N; j++){ if (j>i) { a_5[i][j] = a_5[i][i]; } else { a_5[i][j] = a_5[i][j-1] + a_5[i-j][j-1]; } } } } public static void main(String []args){ partition_123(); partition_4(); partition_5(); for(int i=0; i<N; i++){ for(int j=0; j<N; j++) { System.out.print(a_123[i][j] + " "); } System.out.println(); } System.out.println(); for(int i=0; i<N; i++){ for(int j=0; j<N; j++) { System.out.print(a_4[i][j] + " "); } System.out.println(); } System.out.println(); for(int i=0; i<N; i++){ for(int j=0; j<N; j++) { System.out.print(a_5[i][j] + " "); } System.out.println(); } System.out.println(); System.out.println(a_123[5-2][2]); System.out.println(a_4[5][5]); System.out.println(a_5[5][5]); } }