P2842 纸币问题 1
对应章节：五、数据结构与算法 → （十三） 动态规划（DP）基础。
（一） 任务与输出目标
各面额可无限使用，恰好凑到金额 w，求最少纸币张数。
（二） 建模与推导
定义 dp[s] 为恰好凑出 s 的最少张数。任意方案删去最后一张面额 a 的纸币后，剩余金额为 s-a；替换成该金额的最少张数方案再接回一张，得到 dp[s-a]+1。枚举所有可用面额，取最小值，便得到 dp[s]。
dp[0]=0，其他金额初始为很大的值表示尚未凑出。金额从小到大，每张面额为正，前驱 s-a 已计算；同面额可以多次成为最后一张，所以这是完全背包的最小值版本。答案为 dp[w]。
（三） 手算与过程
面额 1、5、11，金额 15：拿 11 后还需四张 1，共 5；三张 5 只需 3，最优为 3。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
int n, w;
cin >> n >> w;
vector<int> a(n);
for (int& x : a)
cin >> x;
vector<int> dp(w + 1, w + 1);
dp[0] = 0;
for (int s = 1; s <= w; ++s)
for (int value : a)
if (value <= s)
dp[s] = min(dp[s], dp[s - value] + 1); // 删去最后一张，再接回一张。
cout << dp[w] << '\n';
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
时间 \(O(nw)\)，空间 \(O(n+w)\)。