整数划分（三连发）
第一题：
1 样例：如一个正整数5，可以划分为7种：
[5]
[4,1]
[3,2] [3,1,1]
[2,2,1] [2,1,1,1]
[1,1,1,1,1]
2分析：2
将一个正整数n划分，共有多少种划分方式？
上面的例子第一行，所有加数不超过5；
第二行，所有加数不超过4；
........
第五行，所有加数不超过1.
定义 dp[n][m]表示正整数n，所有加数不超过m的划分数目。
3分析m，n：
1、n== 1或m== 1时共1种划分方式dp[n][m] = 1;
2、n== m时dp[n][n]= dp[n][m-1]+1，这样就把主要问题转化为对3的分解。
3、n> m时我们发现只要将dp[n][m-1]加上包含加数m的划分数就等于dp[n][m]。即：dp[n][m]= dp[n][m-1] +包含加数m的划分数。
包含加数m的划分数可以转化为：dp[n-m][m]。所以3可以表示为：
dp[n][m]= dp[n][m-1] + dp[n-m][m]
4、n< m等同于dp[n][n];
4代码：
[cpp] view plaincopy
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1010
int t , k;
int dp[MAXN][MAXN];
void solve(){
memset(dp , 0 , sizeof(dp));
for(int i = 1 ; i <= k ; i++){
for(int j = 1 ; j <= k ; j++){
if(i == 1 || j == 1)
dp[i][j] = 1;
else if(i == j)
dp[i][j] = dp[i][j-1] + 1;
else if(i < j)
dp[i][j] = dp[i][i];
else
dp[i][j] = dp[i][j-1] + dp[i-j][j];
}
}
printf("%d\n" , dp[k][k]);
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d" , &k);
solve();
}
return 0;
}
第二题：
1 样例：5分成2个正整数的和有2种
1 4
2 3
2分析：
定义dp[n][m]表示的是将n分成m部分的方案数，那么这个时候就考虑这个m部分的组成情况
1如果这m部分没有1，那么我们先将m个1分到m份上面，然后在将剩下的n-k分到m部分上，所以就有dp[n][m] = dp[n-m][m];
2如果这m部分有1，那么先将1这个部分扣除，剩下的就是n-1分给m-1部分了，
所以就有dp[n][m] =dp[n-1][m-1];
所以就有dp[n][m]= dp[n-m][m] + dp[n-1]][m-1]；
3注意事项：
当n= m时候dp[n][m]= 1;
当 m= 1时候dp[n][m]= 1;
当 n= 1时候n< m那么dp[n][m]= 0；
4代码：
[cpp] view plaincopy
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
int t , m , n;
int dp[MAXN][MAXN];
void solve(){
int i , j;
memset(dp , 0 , sizeof(dp));
for(i = 1 ; i <= n ; i++)
dp[i][i] = dp[i][1] = 1;
for(i = 1; i <= n ; i++){
for(j = 1 ; j <= m ; j++){
if(i <= j)
break;
if(i != 1 && j != 1)
dp[i][j] = dp[i-j][j] + dp[i-1][j-1];
}
}
printf("%d\n" , dp[n][m]);
}
int main(){
scanf("%d" , &t);
while(t--){
scanf("%d%d" , &n ,&m);
solve();
}
}
第三题：
1 分析：
第一问：
和第一题相同
第二问：
和第二题相同
第三问：
在第一问的基础上大答案为dp[n][k];
第四问(不懂为什么)：
用dp[i][j]表示将i分成j个奇数的方案数，tmpDP[i][j]表示将i分成j个偶数的方案数
那么就有tmpDP[i][j] = dp[i-j][j]; dp[i][j] = dp[i-1][j-1] + tmpDP[i-j][j];
第五问：
0/1背包的变形，有n件物品大小为1,2......n.求将大小为n的背包装满共有几种方案数。
那么就有状态转移方程： dp[i][j] = dp[i-1][j] + dp[i-1][j-i]; (j >= i)
dp[i][j] = dp[i-1][j] (j < i)
2代码：
[cpp]
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
int n , k;
long long dp[MAXN][MAXN];
long long ans;
void solve(){
int i , j;
/*第一个问题dp[i][j]表示将i分成不大于j的方案数*/
memset(dp , 0 , sizeof(dp));
for(i = 1 ; i <= n ; i++){
for(j = 1; j <= n ; j++){
if(i == 1 || j == 1)
dp[i][j] = 1;
else if(i == j)
dp[i][j] = 1 + dp[i][j-1];
else if(i < j)
dp[i][j] = dp[i][i];
else
dp[i][j] = dp[i][j-1] + dp[i-j][j];
}
}
printf("%lld\n" , dp[n][n]);
ans = dp[n][k];/*保存下来作为第三问题的答案*/
/*第二个问题dp[i][j]表示将i分成j部分的方案数*/ <
补充：软件开发 , C++ ,
