322. Coin Change

Leetcode link

解题思路

题目要求我们计算给出的硬币能构成指定金额的最小数量

这种求极值的问题非常适合用动态规划来求解

我们可以构造一个有 amount + 1 个元素的数组 dp，表示构成 0 ~ amount 金额的最小硬币个数

至于状态转移方程，我们考虑到有一个金额 i，我们可以通过遍历硬币的种类来更新 dp[i]

更新的思路是这样的，当我们遇到一个硬币的金额 coin 小于 i 的时候，i 有两种可能：

• 不用这个硬币，也就是 dp[i] = dp[i]
• 用这个硬币，也就是 dp[i] = dp[i - coin] + 1

题目要求我们求最小个数，所以状态转移方程就是

dp[i] = min(dp[i], dp[i - coin] + 1)

最后，我们把 1 ~ amount 金额全部遍历一遍更新 dp 就好了

C++

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1, amount+1);
        dp[0] = 0;

        for(int i=1;i<=amount;i++) {
            for(int coin: coins) {
                if(i >= coin) {
                    dp[i] = min(dp[i], dp[i-coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
};

Javascript

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    let dp = new Array(amount+1).fill(amount+1);
    dp[0] = 0;
    for(let i = 1;i<=amount;i++) {
        for(let coin of coins) {
            if(coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
};