leetcode322.找零钱-蒲公英云

leetcode322.找零钱

请添加图片描述
经典动态规划，迭代法会超时，直接分析动态规划的几个重点
1、状态：dp数组要存什么

对于本题，每个问题可以分解成相同的子问题，具体一点举例，求amout的最小硬币数，转化为求amount-1的最小硬币数等等。。dp数组存的就是amount

2、状态转移方程

具体来看，假设我们有【1，2，5】三种硬币，需要求amount=100的最小硬币数，按照分解的思路，我们要求 max（amount-1最小硬币数+1，amount-2最小硬币数+1，amount-5最小硬币数+1）所以状态转化方程便是
dp[i] = Math.min(dp[i - coin] + 1, dp[i - coin] + 1, ...)
然后可以把coin数组用一个for循环代替变成

for (let j = 0; j < coins.length; j++)
```
{  dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);   
}
```

完整代码

* @param { number} amount
 * @return { number}
 */
var coinChange = function(coins, amount) { 
    if(amount === 0) return 0;
    //初始化长度为amount+1，值为无穷大的数组
    let dp = Array(amount+1).fill(Infinity)
    dp[0] = 0;
    for(let i = 0; i < dp.length; i++) { 
        for (let j = 0; j < coins.length; j++) { 
            // 如果差值小于零
            if (i - coins[j] < 0) continue;
            // 每一个金额最低需要几个硬币
            dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
        }
    }
    console.log(dp)
    if(dp[amount] === Infinity) return -1;
    else return dp[amount] 
};