var coinChange = function(coins, amount) {
    const memo = {}; // 借用闭包来保证 memo不被污染
    
    function dp(amt) {
        if (amt === 0) return 0;
        if (amt < 0) return -1;
        if (memo[amt] !== undefined) return memo[amt];
        
        let result = Number.MAX_SAFE_INTEGER;
        
        for (let coin of coins) {
            const sub = dp(amt - coin);
            if (sub === -1) continue;
            result = Math.min(result, sub + 1);
        }
        
        result = result === Number.MAX_SAFE_INTEGER ? -1 : result;
        memo[amt] = result;
        return result;
    }
    
    return dp(amount);
};

迭代 DP

var coinChange = function(coins, amount) {
    // 1. 创建 DP 数组，初始化为无穷大
    // 长度 amount + 1，保证下标能取到 amount
    const dp = new Array(amount + 1).fill(Infinity);
    
    // 2. 基准条件
    dp[0] = 0;
    
    // 3. 外层循环：遍历所有金额状态（从 1 开始）
    for (let i = 1; i <= amount; i++) {
        
        // 4. 内层循环：遍历所有硬币选择
        for (let coin of coins) {
            
            // 5. 约束条件：当前金额必须能容纳这枚硬币
            if (i - coin >= 0) {
                // 6. 状态转移方程
                // 这里的 dp[i] 是上一轮硬币计算后的值（或者是初始的 Infinity）
                // dp[i - coin] + 1 代表：选择了当前这枚硬币，加上剩余金额的最优解
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    
    // 7. 如果最终结果还是无穷大，说明无法凑出，返回 -1
    return dp[amount] === Infinity ? -1 : dp[amount];
};