题目链接：点击这里
Description
整数划分是一个经典的问题。请写一个程序，完成以下要求。
Input
每组输入是两个整数
Output
对于输入的 n, k
第一行： 将 n 划分成若干正整数之和的划分数。
第二行： 将 n 划分成 k 个正整数之和的划分数。
第三行： 将 n 划分成最大数不超过k的划分数。
第四行： 将 n 划分成若干个奇正整数之和的划分数。
第五行： 将 n 划分成若干不同整数之和的划分数。
第六行： 打印一个空行
Sample Input
5 2
Sample Output
7
2
3
3
3
问题1.将 n 划分成若干正整数之和的划分数
(1) 当
(2) 当
若划分中含有
，在中减去，剩下的就相当于把划分成最大数不超过，即若划分中不含
，就相当于把划分为最大数不超过，即因此，
(3) 当
若划分中含有
，此时划分数为若划分中不含
，就相当于把划分为最大数不超过，即因此，
答案：
问题2.将 n 划分成 k 个正整数之和的划分数
(1) 当
(2) 当
(3) 当
若划分中含有
，就在中减去一个，剩下的就相当于把划分成个正整数，即若划分中不含
，意味着个划分至少为，就将个划分都减去一个，剩下的就相当于把划分成个正整数，即因此，
答案：
问题3.将 n 划分成最大数不超过 k 的划分数
可以发现，该问题的状态表示和状态转移与 问题1 完全相同，两者的区别在于最后答案的取值不同，可以把该题看作 问题1 的特例。
……分析略……
答案：
问题4.将 n 划分成若干个奇正整数之和的划分数
(1) 将
(2)
若划分中含有
，可以将的划分减掉，剩下的就相当于将划分为个奇数，即若划分中不含
，就将个划分都减掉一个1，剩下的就相当于将划分为个偶数，即因此，
答案：
问题5.将 n 划分成若干不同整数之和的划分数
(1) 当
(2) 当
若划分中含有
，那就在中减去一个，由于是互不相同的，所以剩下的就相当于把划分成最大数不超过，即若划分中不含
，意味着划分中每个数都小于，相当于最大数不超过，即因此，
(3) 当
若划分中含有
，此时只有种情况若划分中不含
，意味着划分中每个数都小于，相当于最大数不超过，即因此，
答案：
注意：本题数组一定要开大点！
参考链接：https://www.cnblogs.com/jackge/p/3163835.html
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 110;
int dp[N][N];
int f[N][N];
int g[N][N];
int main()
{
int n, k;
while(~scanf("%d%d", &n, &k))
{
// 问题1.将n划分成若干正整数之和的划分数
memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i < j) dp[i][j] = dp[i][i];
else if(i == j) dp[i][j] = 1 + dp[i][j - 1];
else dp[i][j] = dp[i - j][j] + dp[i][j - 1];
}
}
printf("%d\n", dp[n][n]);
// 问题2.将n划分成k个正整数之和的划分数
memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i < j) dp[i][j] = 0;
else if(i == j) dp[i][j] = 1;
else dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
}
}
printf("%d\n", dp[n][k]);
// 问题3.将n划分成最大数不超过k的划分数
memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i < j) dp[i][j] = dp[i][i];
else if(i == j) dp[i][j] = 1 + dp[i][j - 1];
else dp[i][j] = dp[i - j][j] + dp[i][j - 1];
}
}
printf("%d\n", dp[n][k]);
// 问题4.将n划分成若干个奇正整数之和的划分数
memset(f, 0, sizeof f);
memset(g, 0, sizeof g);
f[0][0] = 1, g[0][0] = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
g[i][j] = f[i - j][j];
f[i][j] = f[i - 1][j - 1] + g[i - j][j];
}
}
int ans = 0;
for(int i = 0; i <= n; i++) ans += f[n][i];
printf("%d\n", ans);
// 问题5.将 n 划分成若干不同整数之和的划分数
memset(dp, 0, sizeof dp);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i < j) dp[i][j] = dp[i][i];
else if(i == j) dp[i][j] = 1 + dp[i][j - 1];
else dp[i][j] = dp[i - j][j - 1] + dp[i][j - 1];
}
}
printf("%d\n\n", dp[n][n]);
}
return 0;
}
