leetcode322. Coin Change

kohoh_ 發布于2019-08-15 14:41 / 1034人閱讀

摘要：傳入的參數為手上有的紙幣的面額以及希望兌換的面額。這里假設紙幣的數量是無窮的。這題本質上考察的是動態規劃思想。這里有兩種動態規劃的方法，分別從遞歸和非遞歸的角度解決這個問題。具體的情況還是要看數據的分布情況來確定選擇哪種方法。

題目要求

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

這里模擬實現了一個換錢算法。傳入的參數為手上有的紙幣的面額以及希望兌換的面額。這里假設紙幣的數量是無窮的。

這題本質上考察的是動態規劃思想。這里有兩種動態規劃的方法，分別從遞歸和非遞歸的角度解決這個問題。具體的情況還是要看數據的分布情況來確定選擇哪種方法。

非遞歸

這里我們新建一個臨時數組result，下標i上的值來存儲用當前手上的紙幣兌換面額i時所需要的最少的紙幣數量。這樣，假設有一個紙幣數組[coin[0], coint[1], ..., coin[k]]，我們需要計算兌換面額i所需要的最小數量的紙幣，那么只需要比較[result[i-coin[0]], result[i-coin[1]], result[i-coin[2]] ... , result[i-coint[k]]]即可。這里需要考慮一些越界情況比如手上紙幣面額比需兌換面額大。還有可能result[i-coin[t]]是無法兌換的。

    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        Arrays.sort(coins);
        if(coins==null || coins.length==0 || amount < coins[0]) return -1;
        int[] result = new int[amount+1];
        for(int i = coins[0] ; i<=amount; i++){
            int tmp = Integer.MAX_VALUE;
            for(int j = 0 ; j
遞歸
這里需要注意的是，用int數組作為一個緩存來減少重復計算的損耗。其實這里的代碼還是可以繼續優化的。
    private int[] cache;
    public int coinChange2(int[] coins, int amount){
        cache = new int[amount];
        return coinChangeRecursive(coins, amount);
    }
    
    public int coinChangeRecursive(int[] coins, int amount){
        if(amount<0) return -1;
        if(amount==0) return 0;
        if(cache[amount-1] != 0) return cache[amount-1];
        int min = Integer.MAX_VALUE;
        for(int coin : coins){
            int res = coinChangeRecursive(coins, amount-coin);
            if(res>=0 && res

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68758.html

[LeetCode] 322. Coin Change

Problem You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount o...

ccj659 2019-08-16 13:37 評論0 收藏0
[LeetCode - Dynamic Programming] Coin Change

摘要：解題思路動態規劃，用表示總價為的最小紙幣張數，很容易想到狀態轉移方程當然前提是要大于紙幣金額數。表示取一張面額加上合計為的最小紙幣數。另題目要求無法合計出的金額，要返回，所以要作特殊處理，否則就會返回元素初始化值代碼 Coin ChangeYou are given coins of different denominations and a total amount of money...

dackel 2019-08-16 10:26 評論0 收藏0
[LeetCode] 518. Coin Change 2

Problem You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infini...

stefan 2019-08-16 13:44 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0
100塊錢換零錢，最多有多少種方式的 JavaScript 版本實現

摘要：原文鏈接歡迎現在有塊錢人民幣，將塊錢換成零錢最小幣值元，一共有多少方式總的不同方式的數目等于將現金數換成除第一種幣值之外的所有其他硬幣的不同方式數據，加上將現金數第一種幣值換成所有種類的幣值的不同方式，根據上面的說法來實現吧實現中的是中的原文鏈接: 歡迎 Star 現在有100塊錢人民幣，將 100 塊錢換成零錢（最小幣值 1 元），一共有多少方式？總的不同方式的數目等于：將現...

xeblog 2019-08-22 10:49 評論0 收藏0