分析
- 本题属于 完全背包问题 的一个应用,只不过状态f的属性从
Max
变成了Count
【空间优化】
观察等式 f[j] = f[j] + f[j - vi]
第一,在计算左边的第i层的f[j]之前,要用到右边的f[j]
,因为f[j]
还没被算出来(正在算)所以右边用来计算的f[j]
是上一层的f[j]
,即f[i - 1][j]
第二,由于 vi > 0
且循环中的j
是从小到大 故 f[j- vi]
一定在f[j]
之前(在当前第i层)被算过了,故f[j - vi]
事实上是 f[i][j-vi]
综上:当前第i层我们正在算的f[j]
= f[i][j] = f[i -1][j] + f[i][j - vi]
,这和之前的二维情形是等价的
dp问题的优化就是看 能否对已有代码做等价变形,所以能够顺利写出朴素版本是看懂甚至熟练掌握优化版本的基础
C++ 代码
【特殊处理】f[0]
的意义是 凑出0元的方案数,显然,凑出0元 = “什么都不凑”,而 “什么都不凑” 本身就是一种方案,故f[0] = 1
(f为全局变量,初始值为0)
#include <cstring>
#include <iostream>
using namespace std;
const int N = 30, M = 10010;
int n, m;
int v[N];
long long f[M];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i];
f[0] = 1;
for (int i = 1; i <= n; i++)
for (int j = v[i]; j <= m; j++)
f[j] += f[j - v[i]];
cout << f[m];
return 0;
}
- 因为每次计算只会用到当前层的v,所以也可以边输入边算
int main() {
cin >> n >> m;
f[0] = 1;
while (n--) {
int v;
cin >> v;
for (int j = v; j <= m; j++)
f[j] += f[j - v];
}
cout << f[m];
return 0;
}