力扣面试08.11题解析：动态规划解决零钱兑换问题（附完整代码与优化思路）
3个月前 (08-28)
一、题目解读
力扣面试08.11题要求计算给定金额n的零钱兑换方案总数，可使用指定面额的硬币（如1、5、10、25），每种硬币无数量限制。需输出总方案数对10^9+7取模的结果。题目核心在于组合计数，需高效处理重复子问题，避免指数级时间复杂度。
二、解题思路
采用动态规划（Dynamic Programming）策略，将问题拆解为子问题组合。定义状态：dp[i]表示金额i的兑换方案总数。核心转移方程基于“最后一步使用的硬币面值”分类，即dp[i] = sum(dp[i-coin])（coin为可用硬币）。通过按面值顺序遍历，确保每个子问题仅被计算一次，避免重复。
三、解题步骤
1. 初始化：设置dp[0]=1（0元无需兑换，方案数为1）。
2. 硬币顺序处理：按固定面值数组[1,5,10,25]顺序遍历，避免组合重复。
3. 动态更新：对每个金额i，遍历硬币coin，若i≥coin则累加dp[i] += dp[i-coin]，并取模防溢出。
4. 结果返回：最终dp[n]即为目标方案数。
四、代码与注释
class Solution {
public:
int waysToChange(int n) {
const int MOD = 1000000007; // 定义取模常数防溢出
vector<int> dp(n + 1, 0); // 初始化dp数组，金额0~n的方案数
dp[0] = 1; // 边界：0分有1种表示法（不选硬币）
// 按硬币面值顺序处理（关键优化点）
int coins[4] = {1, 5, 10, 25};
for (int coin : coins) { // 外层循环：枚举硬币
for (int i = coin; i <= n; ++i) { // 内层循环：金额递增
dp[i] = (dp[i] + dp[i - coin]) % MOD; // 转移方程：当前方案 = 原方案 + 减去coin后的方案
}
}
return dp[n];
}
};注释解析：
● MOD常量：大数取模避免整数溢出。
● dp初始化：强制金额0的方案数为1，作为递归基。
● 双层循环逻辑：外层按面值顺序避免重复组合，内层通过i-coin回溯子问题。
● 取模运算：确保每次累加结果合法。
五、总结
本解法通过动态规划将复杂组合问题转化为线性递推，时间复杂度O(n×硬币数)，空间O(n)。关键在于按面值顺序遍历，保证子问题独立性。代码简洁且优化了溢出风险，适用于面试场景。进一步优化方向可探索空间压缩（如滚动数组）或数学组合公式推导。掌握此类动态规划模板对算法面试中「计数类DP」问题具有通用借鉴价值。
参考：力扣面试题08.11题解
原创内容 转载请注明出处
