用 f[i] 表示凑够 i 元的方案数。f[0] 为凑够 0 元的方案,为一种,即都不选择。
假设我们有 k 种硬币,已经知道了用这 k 种硬币凑够 1元, 2元, 3元 ···· m 元的方案数。
即已知在 k 种硬币的情况下,f[0], f[1], f[2], f[3] ···· f[m]。
增加一种面值为 x 硬币后:
-
$\color{red}{f[0], f[1], f[2] ···· f[x-1] 不会变。}$
-
f[x] 除了原来的方案数,新增了只用一枚 x 硬币的方案。$\color{red}{f[x] = f[x] + 1}$。
-
f[x + 1] 除了原来的方案数,新增了用一枚 x 硬币 和 1 元硬币拼凑的方案, 1 元硬币拼凑的方案数为 f[1]。所以$\color{red}{f[x + 1] = f[x + 1] + f[1]}$。
-
f[x + i] 除了原来的方案数,新增了用一枚 x 硬币 和 i 元硬币拼凑的方案。i 元硬币拼凑的方案数为 f[i]。所以$\color{red}{f[x + i] = f[x + i] + f[i]}$。
所以,新增一种面值为 x 硬币,f[x] ~ f[m] 更新,$\color{red}{每一个 f[i] 更新为 f[i] + f[i - x]。}$
综上:
$\color{red}{初始状态: f[0] = 1, f[1] 到 f[m] = 0。}$
$\color{red}{依次增加硬币的种类,并更新 f。更新规则:}$
$\color{red}{新增一种面值为 x 硬币,f[x] 到 f[m] 更新,每一个 f[i] 更新为 f[i] + f[i - x]。}$
代码如下:
//cpp
#include <iostream>
using namespace std;
const int N = 10010;
long long f[N];//保存拼凑 i 元的方案数
int main()
{
int v, m;
cin >> v >> m;
f[0] = 1;//0 元只有一种方案:一种硬币都不选
while(v--)
{
int money;
cin >> money;
for(int i = money; i <= m; i++)
{
f[i] += f[i - money];//新增一种面值为 money 硬币,f[money] ~ f[m] 更新,每一个 f[i] 更新为 f[i] + f[i - money]。
}
}
cout << f[m];
}
附带解题结果:
有问题直接评论即可。
觉得不错,请点赞支持~
当i等于x的时候,使用两枚x的方案数是在什么情况下加入的
牛
你是我的神!!!
牛!!!
我在csdn上看到更多这种讲解,我也觉得这种更好理解
简洁明了,赞1个
不过我是做一遍忘一遍
这个题解好懂
强