好雨知时节，当春乃发生。
随风潜入夜，润物细无声。
野径云俱黑，江船火独明。
晓看红湿处，花重锦官城。——杜甫
题目一：数的划分
网址：https://www.luogu.com.cn/problem/P1025
题目描述
将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。
例如：n=7，k=3，下面三种分法被认为是相同的。
1, 1, 5;
1, 5, 1;
5, 1, 1.
问有多少种不同的分法。
输入格式
n, k(6<n≤200，2≤k≤6)
输出格式
1个整数，即不同的分法。
输入输出样例
输入
7 3
输出
4
说明/提示
四种分法为：
1, 1, 5;
1, 2, 4;
1, 3, 3;
2, 2, 3.
方法一：搜索
搜索框架不难，可以加记忆化，可以优化和剪枝。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 200 + 5, maxk = 7;
int n, k, d[maxn][maxn][maxk];
int dfs(int p, int cur, int dep)
{
if(p < 0 || dep < 0) return 0;//不符题意
int &ans = d[p][cur][dep];
if(cur * dep > p || cur > n) return ans = 0;//剪枝操作
if(ans != -1) return ans;//记忆化
if(!dep)
{
if(!p) return ans = 1;
return ans = 0;
}
return ans = dfs(p, cur + 1, dep) + dfs(p - cur, cur, dep - 1);//两种选择
}
int main()
{
memset(d, -1, sizeof(d));//初始化，防止重复遍历同一个结点
scanf("%d %d", &n, &k);
printf("%d
", dfs(n, 1, k));
return 0;
}
方法二：动态规划
不难想到令dp[i, j]表示剩余数字为i，划分j段序列之方案总和。显然有：dp[i, j] = sigma{dp[i - l, j - 1] | 0 < l <= i}。
留意到1, 2, 3和2, 3, 1以及2, 1, 3算一种相同的方案（组合），刚刚的转移方程似乎是无法避免这点的。通过调整顺序，我们可以将转移方程的l移到最外层，从而保证没有重复地计算。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 200 + 5, maxk = 10 + 5;
int n, k, dp[maxn][maxk] = {};
int main()
{
scanf("%d %d", &n, &k);
dp[0][0] = 1;
for(int l = 1; l <= n; ++ l)
{
for(int i = l; i <= n; ++ i)
{
for(int j = 1; j <= k; ++ j)
{
dp[i][j] += dp[i - l][j - 1];
}
}
}
printf("%d
", dp[n][k]);
return 0;
}
其实可以更好。
对于该状态，统计个数时我们分两类讨论：划分的数中至少有一个为1和没有一个为1的方案数总和（显然是可以包含所有情况的）。
当至少有一个为1时方案数为：dp[i - 1, j - 1]，因为既然是确定了划分的一个数是1，那么把它减去不影响结果（方案中等价于没有它）。
当没有一个数为1时，显然方案数等于每一个划分出来的数-1（形象地认为：给定i个球装进j个盒子，要求：每个盒子不能为空，那么如果每个盒子都装有多个球，那么从任意一个盒子中取出1个球不影响结果）。
则必有：dp[i, j] = dp[i - 1, j - 1] + dp[i - j, j]，
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 200 + 10;
int n, k, dp[maxn][7];
int main()
{
scanf("%d %d", &n, &k);
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= k; ++ i) dp[i][i] = 1;
for(int i = 1; i <= n; ++ i)
{
for(int j = 1; j <= min(i - 1, k); ++ j)
{
dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j];
}
}
printf("%d
", dp[n][k]);
return 0;
}
题目二：放苹果
网址：http://poj.org/problem?id=1664
题目描述
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分发（5,1,1和1,1,5是同一种方法）
输入格式
第一行是测试数据的数目t（0 <= t <= 20），以下每行均包括二个整数M和N，以空格分开。1＜=M，N＜=10
输出格式
对输入的每组数据M和N，用一行输出相应的K。
输入输出样例
输入
1
7 3
输出
8
输入
3
3 2
4 3
2 7
输出
2
4
2
看到了这道题的区别：允许空集出现了。
但是，n多枚举0。问题易解了！
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#define SIZE 10 + 5
using namespace std;
int m, n, dp[SIZE][SIZE];
int main()
{
int T;
scanf("%d", &T);
while(T --)
{
scanf("%d %d", &m, &n);
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for(int k = 0; k <= m; ++ k)
{
for(int i = k; i <= m; ++ i)
{
for(int j = 1; j <= n; ++ j)
{
dp[i][j] += dp[i - k][j - 1];
}
}
}
printf("%d
", dp[m][n]);
}
return 0;
}
其实可以仿照之前的做法。
有dp[i, j] = dp[i, j - 1] + dp[i - j, j]。留意j的范围是[1, n]，因此，当i < j时，由抽屉原理可得：必有盘子是空的，因此，dp[i, j] = dp[i, i]。
代码如下：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn = 10 + 5;
int m, n, dp[maxn][maxn];
int main()
{
int T;
scanf("%d", &T);
while(T --)
{
scanf("%d %d", &m, &n);
memset(dp, 0, sizeof(dp));
dp[1][1] = 1;
for(int i = 1; i <= n; ++ i) dp[0][i] = 1;
for(int i = 1; i <= m; ++ i)
{
for(int j = 1; j <= n; ++ j)
{
if(i < j) dp[i][j] = dp[i][i];
else dp[i][j] = dp[i][j - 1] + dp[i - j][j];
}
}
printf("%d
", dp[m][n]);
}
return 0;
}