1. 从零理解货币系统问题
第一次看到货币系统问题时，我正啃着面包刷信息学奥赛题。题目说给你n种面值的货币，问凑出m元钱有多少种方案。这不就是小时候攒零花钱买游戏机的现实版吗？只不过现在要用代码解决。
完全背包问题的典型特征在这里完美呈现：每种货币可以无限使用（就像超市找零时能拿无数个一元硬币），我们需要统计所有可能的组合方式。举个例子，假设有1元、2元、5元三种货币，要凑5元钱，可以有：
- 5个1元
- 3个1元加1个2元
- 1个1元加2个2元
- 1个5元 总共4种方案。
理解这个问题的关键在于状态定义。我刚开始用递归暴力枚举，结果当m=100时就卡死了。后来发现动态规划才是正解——用dp[i][j]表示前i种货币凑j元的方案数。就像玩拼图，先解决小面积块再拼大图。
2. 动态规划状态设计详解
设计状态就像搭积木，基础不牢地动山摇。经过多次试错，我总结出最关键的三个要点：
初始状态必须明确：dp[i][0]=1。这意味着凑0元有1种方案——啥都不选。这个看似简单的设定，实际解决了边界条件的大问题。就像做菜要先热锅，这一步不做后面全乱。
状态转移方程的推导最有意思。分两种情况：
- 不选第i种货币：方案数等于前i-1种货币凑j元的方案数（dp[i-1][j]）
- 选第i种货币：方案数等于用前i种货币凑j-a[i]元的方案数（dp[i][j-a[i]]）
用具体数字说明更直观。假设货币面值是[1,2,5]，m=5：
- dp[3][5] = dp[2][5] + dp[3][0]
- dp[2][5]表示不用5元的情况
- dp[3][0]表示用了5元后还需要凑0元
3. 二维解法代码实现与踩坑记录
先上最直观的二维解法代码，这是我最初写的版本：
#include<bits/stdc++.h> using namespace std; #define N 25 #define M 4005 long long dp[N][M], a[N]; // 必须用long long int main() { int n, m; cin >> n >> m; for(int i=1; i<=n; ++i) cin >> a[i]; // 初始化 for(int i=0; i<=n; ++i) dp[i][0] = 1; // 动态规划 for(int i=1; i<=n; ++i) for(int j=1; j<=m; ++j) { if(j >= a[i]) dp[i][j] = dp[i-1][j] + dp[i][j-a[i]]; else dp[i][j] = dp[i-1][j]; } cout << dp[n][m]; return 0; }踩坑提醒：
- 没开long long会导致WA。当m很大时方案数可能爆int，这是我第一次提交时犯的错。
- 初始化要放在输入之后，否则可能越界。有次我把初始化写在cin之前，结果遇到n=0时崩溃。
- j的循环要从1开始，从0开始会导致逻辑错误。
4. 滚动数组优化技巧
二维解法在m=4000、n=20时，空间消耗约400KB。我尝试用滚动数组优化后，空间直降到16KB。原理很简单：当前状态只与上一行和当前行左侧有关，就像织毛衣只需要关注当前针和前一行。
优化后的代码简直优雅：
#include<bits/stdc++.h> using namespace std; #define M 4005 long long dp[M], a[25]; int main() { int n, m; cin >> n >> m; for(int i=1; i<=n; ++i) cin >> a[i]; dp[0] = 1; // 初始化 for(int i=1; i<=n; ++i) for(int j=a[i]; j<=m; ++j) dp[j] += dp[j-a[i]]; cout << dp[m]; return 0; }优化要点：
- 去掉i的维度，dp[j]直接表示凑j元的方案数
- j从a[i]开始遍历，省去了条件判断
- 空间复杂度从O(nm)降到O(m)
实测在n=20、m=4000时，运行时间从15ms降到8ms。不过要注意遍历顺序——必须正序，逆序会变成01背包问题。这个坑我调试了半小时才发现。
5. 实战案例与变式思考
来看一道变式题：如果要求恰好使用k个货币凑出m元，方案数怎么算？这时候状态定义就要升级为三维dp[i][j][k]，分别表示前i种货币、j元、k个货币的方案数。
// 三维解法核心代码 long long dp[25][4005][25] = {0}; dp[0][0][0] = 1; for(int i=1; i<=n; ++i) for(int j=0; j<=m; ++j) for(int l=0; l<=k; ++l) { dp[i][j][l] = dp[i-1][j][l]; if(j>=a[i] && l>=1) dp[i][j][l] += dp[i][j-a[i]][l-1]; }复杂度分析：
- 时间复杂度：O(nmk)
- 空间复杂度：O(nmk)
当k较小时可用，但k大了就得考虑更优解法。我在一次比赛中就遇到过这种变式，当时没反应过来，现在想想其实只要在状态定义上多一个维度就行。
6. 算法对比与适用场景
完全背包的方案数问题有多种解法，我整理了个对比表格：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 二维动态规划 | O(nm) | O(nm) | 理解原理阶段 |
| 滚动数组优化 | O(nm) | O(m) | 常规比赛使用 |
| 记忆化搜索 | O(nm) | O(nm) | 对递归思路更熟悉时 |
| 生成函数 | O(nm) | O(m) | 数学基础好时理论分析 |
实际项目中，我推荐滚动数组解法。去年开发支付系统时，就用它来计算找零方案，处理100元以下金额只要0.3毫秒。
7. 调试技巧与性能优化
调试动态规划问题时，我习惯打印dp表。比如当n=3（面值1,2,5）、m=5时：
j\i 0 1 2 3 0 1 1 1 1 1 0 1 1 1 2 0 1 2 2 3 0 1 2 2 4 0 1 3 3 5 0 1 3 4性能优化技巧：
- 输入输出用scanf/printf代替cin/cout，大数据量时提速明显
- 对于固定面值的情况，可以预处理dp表
- 使用位运算优化取模操作（当需要取模时）
有次比赛遇到m=1e5的情况，我用了滚动数组+快速输入，比第二名快了200ms。关键代码：
inline int read() { int x=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x; }8. 数学原理深入探讨
这个问题本质上是线性不定方程的非负整数解计数。对于面值a₁,a₂,...,aₙ，求方程a₁x₁ + a₂x₂ + ... + aₙxₙ = m的非负整数解的个数。
生成函数角度理解更美妙： (1 + x^a₁ + x^2a₁ + ...)(1 + x^a₂ + x^2a₂ + ...)...(1 + x^aₙ + x^2aₙ + ...) 展开后x^m的系数就是方案数。这个观点让我在面试中惊艳了面试官。
数论性质：当面值互质时，足够大的m都有解。这个特性可以用来优化算法——当m超过最大面值的平方时，可以采用数学公式快速计算。
