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

题目

https://leetcode.com/problems/coin-change/

题解

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

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

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

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

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

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];} }

总结

以上是生活随笔为你收集整理的leetcode 322. Coin Change | 322. 零钱兑换（动态规划）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。