Leetcode — 322. Coin Change(中文)

問題連結: https://leetcode.com/problems/coin-change/

給予一陣列coins包含你擁有的各幣值, 回傳你最少需要多少個硬幣來湊滿要求的金額amount, 若你無法用現有的硬幣來達成, 則回傳-1
可假設同幣值硬幣可以用無限次

限制:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

範例: 
Input: coins = [1,2,5], amount = 11
Output: 3
解釋: 最少可用兩個$5硬幣搭配一個$1湊到$11

想法:

找到對的方法來解題是很重要的, 我在看完題目的第一想法是想說可以用backtracking來找用各種硬幣的所有組合,再選出所用硬幣最少的那個組合
但其實對於解這題來說, 其實非常浪費時間又沒有必要, 因為我們只需要知道硬幣數量就好了, 不需知道實際是由哪些硬幣組成的 (也因此這樣的方法在Leetcode上只過了一半的test cases)

既然我們只需要知道長度, 而一個金額都是由更小的金額來組成的, 比如只要我們找到如何付10元的方法, 那我們如果需要付20元的時候, 是不是就可以參考我們怎麼付10元的組合

因此我選擇用動態規劃來解這題, 我用一個陣列來記錄各金錢值時所需的最少硬幣數量, 所以代表我們如果要湊到$i, 我們最少需要dp[i]個硬幣

程式邏輯:

所有在dp陣列的初始值會需要設一個不可能到達的數字,以表示我們目前還沒找到可以湊到這個金額的硬幣組合, 像是-1, 或任何負數, 或題目一開始給的變數amount+1 都可以 (因為若題目給要我們找amount的時候, 代表最少幣值是1的話, 總共需要amount個硬幣, 因此我們不可能最少硬幣組合數會需要比amount還多)

但dp陣列有幾個位置可以例外

1. 我們將會預設dp[0]為0, 代表我們需要0個硬幣來湊$0
2. 所有在coins陣列裡面所提到的所有幣值 在dp裡面都會是1, 因為我們只需要1個那個幣值的硬幣就可以達到指定金額

在loop中, 我們每輪都會想要找我們在數值是i的時候, 最少可以多少硬幣就能達成
我們每次都只選一個幣值, 在選這個幣值之後, 我們的目標數值也跟著變小, 因此這時候我們將利用動態規劃的好處- 可以利用先前的努力, 來去看我們之前有沒有找到過"目前數值"所需要的最少硬幣數量, 若有, 那代表我們這輪也可以用 我們剛選的那個硬幣 + "剩下數值的最少硬幣組合" 來組成我們現在所需的數值
每個幣值都試過後, 我們就可得用了某個硬幣後, 所需要最少硬幣數量來組成現在數值i了

⚠️在所有邏輯開始前, 我們必須先把一開始拿到的coins陣列 由小到大排列
有兩個好處:
1. 我們若發現我們拿到的最小的幣值 比指定的數值還要大的話, 可直接回傳-1代表我們沒有辦法用現有硬幣湊錢
2. 當我們發現 “現在位置的硬幣值”是大於 “現在我們要找的數值”時, 我們也可以直接放棄再去拿後面其他幣值的組合們了

👷來看例子當我們有這幾個幣值 coins = [2,3,5].

⚠️在真正的程式裡面, 我們需要從數值1一個一個到目標數值, 找各個數值所需要的最少硬幣數, 但因為我只是想給一個小例子, 我將只會介紹我們在某個數值時候找硬幣組合的過程, 並不會介紹一個一個找每個數值

假設我們現在已經找到$6了, 代表我們前面已經找玩$0~$5所需要花的最少硬幣數量

🔧Step 1. 我們先指定拿第一個硬幣$2, 因此目標數值剩下$4, 我們就會找我們之前在找$4的時候需要幾個硬幣, 查完後發現$4的時候需要兩個硬幣, 因此再加上我們這次已拿的第一個硬幣, 我們目前最少需要3個硬幣才能組成$6

🔧Step 2. 我們第一個硬幣換拿$3, 目標數值剩下$3, 因為我們若要存到$3的時候只需要1個硬幣, 因此再加上去後發現我們這樣的組合只要2個硬幣就可以組成$6

🔧Step 3. 第一個硬幣改拿$5, 目標數值剩$1, 但我們紀錄中 找不到湊成$1的硬幣組, 因此放棄先拿$5的這個組合

🚧試完所有硬幣, 這輪也就結束了, 將會繼續下一個數值 直到我們輪完目標amount

以下為11ms 程式碼, 贏過 87% —

public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        if(amount!=0 && coins[0]>amount)
            return -1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp,-1);
        dp[0] = 0; 
        for(int coin: coins)
        {
            if(coin>amount)
                break;
            dp[coin] = 1;
        }
        for(int i=1;i<=amount;i++)
        {
            if(dp[i]==1)
                continue;
            int minCount = Integer.MAX_VALUE;
            for(int coin: coins)
            {
                if(coin>i)
                    break;
                if(dp[i-coin]==-1)
                    continue;
                minCount = Math.min(minCount, 1+dp[i-coin]);
            }
            if(minCount == Integer.MAX_VALUE)
                dp[i] = -1;
            else
                dp[i] = minCount;
        }
        return dp[amount];
    }

時間複雜度: O(n); 空間複雜度: O(n)