非常难想的题，感觉如果是第一次做的话很难做出来了。
这里问的其实有三个问题，而且相对独立，所以要分开求解。
1.整数n拆成k个正整数
dp[i][j]代表整数 i 拆成k个正整数有多少拆法，那转移方程是dp[i][j] = dp[i-j][j] + dp[i-1][j-1]
这一点我觉得基本上是想不到的。我们转移的时候把所有用j个数组成i的方案分成两类，一类是这j个数里面有至少一个1；另一类是这j个数里面都大于1。那如果这j个数都大于1，那问题就等价于dp[i-j][j]（把所有方案对应的j个整数都减一就行了），再考虑至少有一个1的话那就拿走一个1变成dp[i-1][j-1]。
这里有一点很巧妙是避免了重复的问题，比如把5拆成1+3+1和1+1+3算成两种。
它这么转移保证了不会重复，因为有1的方案一定与没有1的方案不重复！
2.挑若干个不同正整数凑成n
这是个01背包问题，前提是能看出来
3.挑若干个正奇数凑成n
dp[i][j]代表前i个数拆成j个奇数的拆法。跟整数拆分相似，考虑有没有1。不过没有一的话我们要减2*j而不是j，因为没有1的话，最小的就是3往上了
边界条件是dp[i][1]，i为奇数那就是1，为偶数就是0
那dp[i][j] = dp[i-2*j][j] + dp[i-1][j-1]
===2018.9.7===
为什么不能像1里面是dp[i-j][j]呢，因为原来的dp[i][j]是用j个奇数组成i，然后我们枚举最小的组成i的数是不是1，如果是的话，那就所有的都减1，但因为都是用奇数凑的，都减一的话就都剩偶数了，那dp[i-j][j]应该是用j个偶数凑成i-j，这样才与原问题是等价的。但用dp[i-2*j][j]就很好的解决了这个问题。（核心就是通过考虑最小的有没有1来将问题化简成一个范围更小的等价问题。【与以前做的大多数dp不一样，以前的是强调上一个状态是怎么【转移】过来的，但这一题是强调等价问题，也是这题难的地方】）
或者说转移的核心就是等价
1 #include<iostream> 2 #include<cstring> 3 using namespace std; 4 5 int memo1[55][55],memo2[55][55],cost[55],dp[55][55]; 6 7 int dp1(int n,int k){//整数为n拆成k份 8 if(memo1[n][k]!=-1) return memo1[n][k]; 9 if(n==k) return memo1[n][k]=1; 10 if(k==1) return memo1[n][k]=1; 11 if(n>=k+k) return memo1[n][k]=dp1(n-k,k)+dp1(n-1,k-1); 12 return memo1[n][k]=dp1(n-1,k-1); 13 } 14 15 int dp2(int n,int choose){//从前choose个整数里挑，凑成n 16 if(n==0) return memo2[n][choose]=1; 17 if(choose==0) return memo2[n][choose]=0; 18 if(n>=cost[choose]) return memo2[n][choose]=dp2(n-cost[choose],choose-1)+dp2(n,choose-1); 19 return memo2[n][choose]=dp2(n,choose-1); 20 } 21 22 23 int main(){ 24 25 for(int i=1;i<55;i++) cost[i]=i; 26 27 int n,k; 28 while( scanf("%d",&n)!=EOF ){ 29 memset(memo1,-1,sizeof(memo1)); 30 cin>>k; 31 cout<<dp1(n,k)<<endl;//问题1 32 cout<<dp2(n,n)<<endl;//问题2 33 //N划分成若干个奇正整数之和的划分数目 34 //dp[i][j]代表i划分成j个奇正整数之和的数目 35 for(int i=1;i<=n;i++){ 36 if(i%2) dp[i][1]=1; 37 else dp[i][1]=0; 38 } 39 40 for(int i=2;i<=n;i++){ 41 for(int j=2;j<=i;j++){ 42 if( i>=2*j+j ) dp[i][j] = dp[i-2*j][j]+dp[i-1][j-1]; 43 else dp[i][j]= dp[i-1][j-1]; 44 } 45 } 46 int cnt=0; 47 for(int i=1;i<=n;i++) cnt+=dp[n][i]; 48 cout<<cnt<<endl; 49 } 50 51 return 0; 52 }