322. Coin Change - Medium

前往題目

搬運~

想法

• 這應該算是我第一個正式想過的dynamic programming題目了
• 難到爆
• 期待融會貫通的那天
• 答案幾乎只能用抄的

思路

1. 用DP
2. bottom up的方式從amount是0的時候開始，因為amount為0一定是用0個硬幣
3. 從amount為1循環到amount本身
4. 每個循環都檢查每個coin是否能被納入考量，amount - coin為正整數時就代表可能可以被當作答案
5. 於是dp[amount]和1 + dp[amount - coin]取兩數最小值(加一是加coin的意思)
6. 如此就能從0建立，一步步推出amount的答案

下次應該依然還是不會:D

Code

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount < 0 || coins.length == 0 || coins == null) {
            return 0;
        }

        int[] dp = new int[amount + 1];

        Arrays.fill(dp, amount + 1); // Fill with MAX value
        dp[0] = 0; // amount 0 needs 0 coin denomination

        // Go through every possible amount(bottom up)
        for (int a = 1; a <= amount; ++a) {
            // Check every coin to see if possible
            for (int coin : coins) {
                // If not negative, then it's possible
                if (a - coin >= 0) {
                    // +1 is this coin, remember we are counting coins number
                    dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
                }
            }
        }

        return dp[amount] != amount + 1 ? dp[amount] : -1;
    }
}

2024/01/20

• 果然寫不出來，不過比起第一次寫，就算看了答案還是不懂，這次有看懂了
• 只是下次應該大機率還是想不出來…