完全背包解法
- 状态表示:
f[i][j]
表示从[1, i]
中选,体积恰好为j
的方案数 - 状态计算:
按照i
选了0个,1个,2个,…,s个划分
f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2i] + ... +f[i-1][j-s*i]
f[i][j-i] = f[i-1][j-i] + f[i-1][j-2i] + ... +f[i-1][j-s*i]
将两式合并,得
f[i][j] = f[i-1][j] + f[i][j-i]
从而避免了枚举s
- 优化:
观察f[i][j] = f[i-1][j] + f[i][j-i]
,发现f[i-1][j]
和f[i][j-i]
都是在f[i][j]
之前计算出来的, 仅仅和之前计算过的状态相关
故降成一维仅需从小到大枚举
f[j] = f[j] + f[j-i]
- 注意:
什么都不选的方案数为1
二维
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N];
int main()
{
int n;
cin >> n;
//初始化,什么都不选方案数为1
for (int i = 0; i <= n; i ++) f[i][0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (j >= i)
f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod;
else
f[i][j] = f[i - 1][j];
}
cout << f[n][n] << endl;
return 0;
}
一维
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N];
int main()
{
int n;
cin >> n;
//初始化,什么都不选方案数为1
f[0] = 1;
for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++)
{
f[j] = (f[j] + f[j - i]) % mod;
}
cout << f[n] << endl;
return 0;
}
其他解法
- 状态表示:
f[i][j]
表示选了i个数,恰好和为j的方案数 - 状态计算:
划分依据:选的数中最小值为1 或 大于1
若选择的数中最小值为1,去掉一个1后,变成选了i-1
个数,恰好和为j-1
的方案数
若选择的数中最小值大于1,每个数减去1后,变成选了i
个数,恰好和为j-i
的方案数
故
f[i][j] = f[i - 1][j - 1] + f[i][j - i]
按照和从小到大枚举
#include <iostream>
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int f[N][N];
int main()
{
int n;
cin >> n;
//选1个数且总和为1的方案数为1
f[1][1] = 1;
for (int j = 2; j <= n; j ++)
for (int i = 1; i <= j; i ++)
f[i][j] = (f[i - 1][j - 1] + f[i][j - i]) % mod;
int res = 0;
for (int i = 1; i <= n; i ++) res = (res + f[i][n]) % mod;
cout << res << endl;
return 0;
}
其他解法中f[i][j]表示错了吧?视频中是表示所有总和是i,并且恰好表示成j个数的和的方案吧
所以我改了一下
i
和j
的的循环顺序,j
在外层循环