leetcode322.找零钱

妖狐艹你老母 2022-09-03 07:21 190阅读 0赞

![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]  
经典动态规划，迭代法会超时，直接分析动态规划的几个重点  
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] 
    };

时间复杂度Omn  
空间复杂度On

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20220829/b0fd3668a69e46b18c8a709b49ac4248.png