AcWing 900. 整数划分
原题链接
简单
作者:
acw_yxy
,
2021-01-21 16:12:12
,
所有人可见
,
阅读 366
计数dp
(计数dp) $O(n^2)$
C++ 代码
// f[i][j]代表前i个数里选出来和为j这么多的情况的数目
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
const int mod = 1e9+7;
int f[N][N];
int ff[N];
int main()
{
int n;
cin >> n;
f[0][0] = 1;
// 第一版本
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= n; j ++)
{
f[i][j] = f[i-1][j];
for(int k = 1; k * i <= j; k ++)
f[i][j] = (f[i][j] + f[i-1][j - k * i]) % mod;
}
cout << f[n][n]
// 第二个版本
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= n; j ++)
{
f[i][j] = f[i-1][j];
if(j >= i) f[i][j] = (f[i-1][j] + f[i][j-i]) % mod;
}
cout << f[n][n]
// 第三个版本 减小为一唯数据
ff[0] = 1;
for(int i = 1; i <= n; i ++)
for(int j = i; j <= n; j ++)
{
ff[j] = (ff[j] + ff[j-i]) % mod;
}
cout << ff[n];
return 0;
}
请问为啥只初始化f[0][0]=1;f不是表示所有从前i个中选体积恰好为j的方案数量吗?那从前i个物品选且体积恰好为0不应该都是只有一种方案吗
代码里有一句话叫f[i][j] = f[i-1][j];