前言
AcWing算法提高课内容，本文讲解 动态规划
本篇包括以下题目：
⭐️ AcWing 11. 背包问题求方案数
⭐️ AcWing 1023. 买书
⭐️ AcWing 1021. 货币系统
⭐️ AcWing 532. 货币系统
写博客有哪里不完善的地方或者有哪里表达错误希望大家提出来，博主会立即改正！望大家海涵
本文需要先自修基础：背包问题
注：本文中的所有代码全部为优化后的代码，且不提供优化解释，解释请见：背包问题，其中有详细的解释。
背包问题求方案数
题目要求
题目描述：
输入格式：
输出一个整数，表示 方案数 模109+7的结果。
数据范围：
输入样例：
4 5 1 2 2 4 3 4 4 6
输出样例：
2
思路分析
if (f[i][j] == f[i - 1][j]) g[i][j] = (g[i][j] + g[i - 1][j]) % mol; if (j >= v[i] && f[i][j] == f[i - 1][j - v[i]] + w[i]) g[i][j] = (g[i][j] + g[i - 1][j - v[i]]) % mol;
下面代码为一维优化后的代码
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010, mol = 1e9 + 7; int f[N]; int g[N]; int main() { int n, m; cin >> n >> m; g[0] = 1; for (int i = 1; i <= n; i ++ ) { int v, w; cin >> v >> w; for (int j = m; j >= v; j -- ) { int maxv = max(f[j], f[j - v] + w); int temp = 0; if (maxv == f[j]) temp = (temp + g[j]) % mol; if (maxv == f[j - v] + w) temp = (temp + g[j - v]) % mol; f[j] = maxv, g[j] = temp; } } int res = 0; for (int i = 0; i <= m; i ++ ) if (f[i] == f[m]) res = (res + g[i]) % mol; cout << res << endl; return 0; }
买书
题目要求
题目描述：
小明手里有 n 元钱全部用来买书，书的价格为 10 元，20 元，50 元，100 元。
问小明有多少种买书方案？（每种书可购买多本）
输入格式：
一个整数 n,代表总共钱数。
输出格式：
一个整数，代表选择方案种数。
数据范围：
0≤n≤1000
输入样例1：
20
输出样例1：
2
输入样例2：
15
输出样例2：
0
输入样例3：
0
输出样例3：
1
思路分析
f[i]代表恰好用了 i 元钱的时候的方案数
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int w[] = {10, 20, 50, 100}; int f[N]; int main() { int n; cin >> n; f[0] = 1; for (int i = 0; i < 4; i ++ ) for (int j = w[i]; j <= n; j ++ ) f[j] += f[j - w[i]]; cout << f[n] << endl; return 0; }
思考
本题的 AC代码是先枚举的四种金钱，后枚举的体积，那么反过来是否可以呢？
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1010; int w[] = {10, 20, 50, 100}; int f[N]; int main() { int n; cin >> n; f[0] = 1; for (int i = 1; i <= n; i ++ ) for (int j = 0; j < 4; j ++ ) if (i >= w[j]) f[i] += f[i - w[j]]; cout << f[n] << endl; return 0; }
答案是不可以！这是因为如果是第二种代码的话，会有重复计算的结果，比如花 30 元买书的话，第二种情况下，先花钱买一本 10 元的书、再花钱买一本 20元的书，和先花钱买一本 20 元的书、再花钱买一本 10元的书，这显然应该是一种情况的，但是却计算了两次。
