題目

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. 零钱兑换（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。