力扣322——零錢兌換頭條網

2021-03-28 03:00:11 佚名

這道題主要涉及動態規劃，利用這個，就能很好解決這個問題。

原題

給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回 -1。

示例 1:

<code>輸入:
 coins
 =
 [1,
 2
,
 5
],
 amount
 =
 11
輸出:
 3 
解釋:
 11
 =
 5
 + 
 5
 +
 1
/<code>

示例 2:

<code>輸入: coins = [2], amount = 3
輸出: -1
/<code>

說明:

你可以認為每種硬幣的數量是無限的。

原題url：
https://leetcode-cn.com/problems/coin-change/

解題

求出所有可能

我們可以從小到大，求出由當前硬幣，組成所有金額的最小數，這樣最終就是最大金額所能組成的最小硬幣數量。

這種方法核心思想就是記錄所有中間狀態的結果，如果在實際使用中，你的傳入參數amount是不斷變化的，那麼用這種方法會比較方法，因為之前的結果可以被重複利用，這樣也是一種優勢。

現在我們來看看代碼：

<code>
class
 Solution
 {
    
public
 int
 coinChange
(
int
[] coins, int
 amount)
 {
         
        Arrays.sort(coins);

         
        int
[] result = new
 int
[amount + 1];
        result[0
] = 0;
         
        for
 (int
 currentAmount = 1; currentAmount <= amount; currentAmount++) {
            int minNum = Integer.MAX_VALUE;
             
            for
 (int
 j = 0 
; j < coins.length; j++) {
                 
                int remainAmount = currentAmount - coins[j];
                if
 (remainAmount 0) {
                    break;
                }

                 
                if (result[remainAmount] == Integer.MAX_VALUE) {
                    continue;
                }

                 
                minNum = Math.min(minNum, result[remainAmount] + 1);
            }

            result[currentAmount] = minNum;
        }

        return
 result[amount] == Integer.MAX_VALUE ? -1 : result[amount];
    }
}/<code>

提交OK，執行用時：12 ms，內存消耗：36 MB，只超過了83.24%的 java 提交，看來還有優化的空間。

動態規劃優化

倒不是說動態規劃就一定比上面的方法更加優秀，只是也是一種思想，可以利用 dfs(深度優先搜索) 或者 bfs(廣度優先搜索)，我下面這種寫法是 dfs，因為是一路進行到底之後，再去考慮其他情況的。(補充一點，如果使用 bfs 的話，可以藉助隊列來實現非遞歸的形式。)

所謂的優化，就是從硬幣的使用上來說，從面值大的開始，並且從可以使用數量最大的開始。與此同時，我們也記錄了最小使用數量，如果用當前面值最大的硬幣並且使用最多時，依舊大於最小值，那麼就不用繼續查找了。

以上的優化，其實是和題目相關聯，雖然不能用在其他的題目上，但也可以作為一種思想，值得我們借鑑和學習。

接下來我們看看代碼：

<code>
class
 Solution
 {
    private
 int minCount = Integer.MAX_VALUE;

    
public
 int
 coinChange
(
int
[] coins, int
 amount)
 {
         
        Arrays.sort(coins);
         
        helper(coins, coins.length - 1
, 0, amount);
        return
 minCount == Integer.MAX_VALUE ? -1 : minCount;
    }

    
private
 void
 helper 
(
int
[] coins, int
 coinIndex, int
 curCount, int
 amount)
 {
        if
 (coinIndex 0) {
            return;
        }
         
        if
 (amount % coins[coinIndex] == 0) {
            minCount = Math.min(minCount, curCount + amount / coins[coinIndex]);
            return;
        }

         
        for
 (int
 i = amount / coins[coinIndex]; i >= 0; i--) {
             
            if
 (curCount + i + 1 >= minCount) {
                break;
            }
            
            helper(coins, coinIndex - 1, curCount + i, amount - i * coins[coinIndex]);
        }
    }
}/<code>