leetcode 322. Coin Change | 322. 零钱兑换（动态规划）

向右看齐 2022-10-20 00:55 213阅读 0赞

## 题目 ##

[https://leetcode.com/problems/coin-change/][https_leetcode.com_problems_coin-change]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

也许是第一次在没看答案的情况下写的动态规划…

第一反应是，这题不是广义背包吗？想了一下，不是，因为广义背包的约束是小于等于容量，而本题的约束是等于容量。

第二反应是，这题有点像 dp 的累加和啊。把一个数 `a` 可以拆成 `b + c`，这样就划分成了子问题。

第三反应是，拆分的过程有点类似于 [**线段树**][Link 1]，可以用来方便理解，不过思路不能照搬。

结合这三个想法，确定了 **dp\[\] 表示强制包含当前元素情况下，需要的最小硬币数量**，然后就开始草稿尝试 dp 了。写了几行之后，发现思路可行，搞定。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public int coinChange(int[] coins, int amount) { 
            Arrays.sort(coins);
            int[] dp = new int[amount + 1]; // 强制包含当前元素情况下，需要的最小硬币数量
            for (int i = 1; i < amount + 1; i++) { 
                int minCount = Integer.MAX_VALUE;
                for (int coin : coins) { 
                    if (coin >= i) { 
                        if (coin == i) minCount = 1;
                        break;
                    }
                    if (dp[i - coin] != Integer.MAX_VALUE)
                        minCount = Math.min(minCount, 1 + dp[i - coin]);
                     // minCount = Math.min(minCount, dp[coin] + dp[i - coin]);
                }
                dp[i] = minCount;
            }
            if (dp[amount] == Integer.MAX_VALUE) return -1;
            else return dp[amount];
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

[https_leetcode.com_problems_coin-change]: https://leetcode.com/problems/coin-change/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20221004/92c115ef53ce451c907394f087f2718d.png
[Link 1]: https://hanquan.blog.csdn.net/article/details/118525229
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20221004/c912ba742367416a97964e9b11264904.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20221004/da5918f5e1034687bc8e6fabf7153c20.png