力扣HOT100（50）动态规划-零钱兑换

动态规划核心思路（一句话讲透）

用dp[i]表示凑成金额 i 所需的最少硬币个数。 对于每个金额i，我们可以尝试使用每一种硬币：

• 如果硬币面额coin <= i，那么我们可以用这个硬币，剩下的金额就是i - coin
• 凑成i的最少硬币数 = 凑成i - coin的最少硬币数 + 1（当前这个硬币）
• 我们在所有可能的硬币中，取硬币数最少的那个

所以状态转移方程：

plaintext

dp[i] = min(dp[i], dp[i - coin] + 1) （当 coin <= i 时）

三、完整解题步骤

1. 处理边界情况

• 如果amount == 0：直接返回0
• 如果coins为空且amount > 0：直接返回-1

2. 初始化 dp 数组

• 数组长度为amount + 1（因为要凑 0 到 amount 共 amount+1 个金额）
• 所有元素初始化为一个不可能达到的大值：amount + 1
  • 为什么用amount + 1？因为最多需要amount个 1 元硬币，所以amount + 1是一个永远不可能达到的数，用来表示 “这个金额暂时无法凑成”
  • 不要用INT_MAX，否则dp[i - coin] + 1会溢出
• dp[0] = 0：凑成 0 元需要 0 个硬币（这是所有推导的基础）

3. 遍历计算 dp 数组

• 外层循环：遍历所有金额，从1到amount
• 内层循环：遍历所有硬币面额
  • 如果当前硬币面额coin <= i（可以用这个硬币）
  • 按照状态转移方程更新dp[i]：dp[i] = min(dp[i], dp[i - coin] + 1)

4. 结果判断

• 如果dp[amount] > amount：说明这个金额无法凑成，返回-1
• 否则返回dp[amount]

class Solution { public: int coinChange(vector<int>& coins, int amount) { int Max = amount+1;//因为待会要比较最小值 所以初始化尽可能大，最大面值是amount，所以amount不可能达到 vector<int> dp(amount + 1,Max);//长度amount+1，所有值初始化为amount+1 dp[0] = 0; for(int i =1;i<= amount;i++){//遍历面额的所有构成 比如11块：1块、2块 for(int j =0;j<(int)coins.size();j++){//遍历所有的硬币 if(coins[j]<=i){//如果这个硬币面额比当前面额小 才能用 //当前这个面额等于下面的公式 dp[i] = min(dp[i],dp[i-coins[j]]+1); //总硬币数 = 凑i-coin的硬币数 + 1 。这个就是先用这个小额的硬币一次，然后再和 当前面额-硬币面额 需要的数量求和。 } } } return dp[amount] > amount ? -1:dp[amount];//判断是否满足，如果最后的数量大于amount凑不出来，因为最大就是和amount数量一样的一块钱构成的。满足条件就返回 } };