NYOJ 571整数划分(三)【DP】
整数划分是一个经典的问题。请写一个程序,完成以下要求。
5 2
72333输出提示:1.将5划分成若干正整数之和的划分为： 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+12.将5划分成2个正整数之和的划分为： 3+2, 4+13.将5划分成最大数不超过2的划分为： 1+1+1+1+1, 1+1+1+2, 1+2+24.将5划分成若干 奇正整数之和的划分为： 5, 1+1+3, 1+1+1+1+15.将5划分成若干不同整数之和的划分为： 5, 1+4, 2+3
这两天搞动态规划搞得头疼，关键是自己的做题太少，思维容量太小，见到题目，不能够很快的有一个思路，导致自己像无头苍蝇一样，看来以后还得多多刷题，多多AC，只有量的积累，才有质的飞跃，加油。
看了两天的整数划分，NYOJ上的（一）（二）以前写过，用的是递归，看的是结题报告，朦朦胧胧的，这次无意间在网上看到这个题，就尝试着写了一遍，艾玛，惨不忍睹啊，
然后搜了无数大牛的博客后，终于找到了一点思路，然后，按照这个思路往下写，终于看起来像那么回事了
思路:
dp[i][j]表示要被分的数为i,最大数不超过j的划分数.
当 j>i 时当然是只能j分到i而已.
当 i>=j 时，注意到 5 = 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1,5可以划分为4+1,而4的划分数之前已求出,相当于加上4的划分数,即dp[i][j-1];
另外注意到5 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1，即还要加上要减的数5减掉2之后,dp[5][2] = dp[5-2][2]+dp[5][1] = dp[3][2]+1 = dp[3-2][2]+dp[3][1]+1 = dp[1][1]+1+1 = 3;
每次算dp时其实都可以先写写dp之间的转移关系，弄清楚后，再写出状态转移方程
所以,对于前三行,根据状态转移方程很容易写出：
dp[i][j] = dp[i][i] (j>i)
= dp[i-j][j] + dp[i][j-1] (i<=j)
第一行:将n划分成若干正整数之和的划分数。
dp[n][n] ;
第二行:将n划分成k个正整数之和的划分数。
dp[n-k][k] ;
第三行:将n划分成若干最大不超过k的正整数之和的划分数。
dp[n][k] ;
第四行：将n划分成若干奇正整数之和的划分数。
dp[i][j]是当前的划分数为i,最大值为j时的中的划分数，则状态转移方程为
dp[i][j] = dp[i][i] if( j>i && j%2 == 1)
= dp[i][i-1] if( j>i && j%2 == 0)(最大数不可能为偶数)
= dp[i-j][j] + dp[i][j-2] 没用到j时划分不变，即dp[i][j-2],用到则是dp[i-j][j];
第五行：将n划分成若干完全不同正整数之和的划分数。
其实这个就是一个背包,状态转移方程为:
dp[i][j] = dp[i][j-1]+dp[i-j][j-1] 其中dp[i][j-1]为不选择j时的方案,dp[i-j][j-1]为选择j时的方案
为了加深对本题的理解，以及对DP的理解，我把这个题目上传到了我们学校的OJ上了，欢迎大家来练习~~
题目地址:http://acm.nyist.net/JudgeOnline/problem.php?pid=571
我的代码:
#include <stdio.h>#define N 52int dp[N][N] = {0} , dp1[N][N] = {0} , dp2[N][N] = {0} ;void Divid(){ dp[0][0] = 1 ; for( int i = 0 ; i < N ; i++ ) for( int j = 1 ; j < N ; j++ ){ if( i < j ) dp[i][j] = dp[i][i] ; else dp[i][j] = dp[i-j][j] + dp[i][j-1] ; }}void Divid1(){ for( int i = 1 ; i < N ; i++ ) dp1[i][1] = 1 ; //最大值为1时只能有本身组成,Answer为1 for( int i = 1 ; i < N ; i+=2 ) dp1[0][i] = 1 ; dp1[0][0] = 1 ; for( int i = 1 ; i < N ; i++ ) for( int j = 3 ; j < N ; j+=2 ){ if( j > i ){ if( i&1 ) dp1[i][j] = dp1[i][i] ; else dp1[i][j] = dp1[i][i-1] ; } else dp1[i][j] = dp1[i-j][j] + dp1[i][j-2] ; }}void Divid2(){ for( int i = 1 ; i < N ; i++ ){ dp2[0][i] = 1 ; dp2[1][i] = 1 ; } for( int i = 2 ;i < N ; i++ ) for( int j = 1 ;j < N ; j++ ){ if( j > i ) dp2[i][j] = dp2[i][i] ; else dp2[i][j] = dp2[i-j][j-1] +dp2[i][j-1] ; }}int main(){ int n , k ; Divid() ; Divid1() ; Divid2() ; while( ~scanf( "%d%d" , &n , &k ) ){ printf( "%d\n" , dp[n][n] ) ; printf( "%d\n" , dp[n-k][k] ) ; printf( "%d\n" , dp[n][k]) ; printf( "%d\n" , n&1 ? dp1[n][n] : dp1[n][n-1] ) ; printf( "%d\n\n" , dp2[n][n]) ; } return 0;}