AcWing 900. 整数划分-计数dp做法
原题链接
简单
作者:
rushhhhh
,
2021-02-28 17:08:11
,
所有人可见
,
阅读 354
#include <iostream>
#include <algorithm>
using namespace std;
/*
状态表示f[i,j]
集合:总和为i,总个数为j的方案
属性:cnt
状态计算
把集合分为最小值是1的和最小值不是1的,则
最小值是1,即f[i-1,j-1]
最小值不是1,即f[i-j,j]
将所有数都减去1,则此方案集合在数量上等价于
总和是i-j,总个数还是j的方案集合
因此,f[i,j] = f[i-1,j-1] + f[i-j,j]
*/
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int main()
{
cin >> n;
// 初始化总和为1,总个数为1的方案(当然只有{1}这一种情况)
f[1][1] = 1;
for(int i=2; i<=n; i++)
for(int j=1; j<=i; j++)
f[i][j] = (f[i-1][j-1] + f[i-j][j]) % mod;
// 统计总和为n的所有不同个数的方案数
int res = 0;
for(int i=1; i<=n; i++)
res = (res + f[n][i]) % mod;
cout << res;
return 0;
}