描述
题解
这个题以前做的时候使用 dfs() 搜索做的,但是标程是 dp。
先设 dp[i][j] 表示数 i 分为 j 份时的总方案数。
考虑到 dp[i][j] 的状态可以由包含 1 的上一个状态和不包含 1 的上一个状态转移而来,所以我们可以考虑,不包含 1 的情况我们加一份 1,而包含 1 的情况,我们给每一份都加 1,所以状态转移方程也就变为了:
dp[i][j]=dp[i−j][j]+dp[i−1][j−1];
复杂度 O(nk) ,绿色快捷环保!比搜索来的快得多……
代码
#include <iostream>
using namespace std;
const int MAXN = 222;
const int MAXK = 9;
int dp[MAXN][MAXK];
int main(int argc, const char * argv[])
{
int n, k;
cin >> n >> k;
dp[1][1] = 1;
for (int i = 2; i <= n; i++)
{
for (int j = 1; j <= k; j++)
{
if (i >= j)
{
dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
}
}
}
cout << dp[n][k] << '\n';
return 0;
}