[LeetCode] 518. Coin Change 2

stefan 發布于2019-08-16 13:44 / 1403人閱讀

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 infinite number of each kind of coin.

Note: You can assume that

0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
 

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
 

Example 3:

Input: amount = 10, coins = [10] 
Output: 1

Solution DP

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for (int coin: coins) {
            for (int i = 1; i <= amount; i++) {
                if (i - coin >= 0) dp[i] += dp[i-coin];
            }
        }
        return dp[amount];
    }
}

DFS - TLE

class Solution {
    int count = 0;
    public int change(int amount, int[] coins) {
        if (amount == 0) return 1;
        dfs(coins, 0, 0, amount);
        return count;
    }
    private void dfs(int[] coins, int start, int sum, int amount) {
        if (start == coins.length) return;
        if (sum == amount) {
            count++;
            return;
        }
        for (int i = start; i < coins.length; i++) {
            if (coins[i] + sum > amount) continue;
            else dfs(coins, i, sum+coins[i], amount);
        }
    }
}

GPU云服務器云服務器 Coin 518vps coin 域名行情 change

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

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

leetcode322. Coin Change

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

kohoh_ 2019-08-15 14:41 評論0 收藏0
[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
100塊錢換零錢，最多有多少種方式的 JavaScript 版本實現

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

xeblog 2019-08-22 10:49 評論0 收藏0
koa2開發微信公眾號: 不定期推送最新幣圈消息

摘要：背景比特幣說好的分叉最后卻分叉不成，如今算力又不夠，于是比特現金想篡位沒一個星期就漲了快倍，錯過這趟快車甚是后悔，于是打算寫一個可不定期推送最新消息的微信公眾號。既然是利用微信這個平臺載體，當然要熟悉微信的，遂封裝了一下。背景：比特幣說好的segwit2x分叉最后卻分叉不成，如今算力又不夠，于是比特現金想篡位? 沒一個星期就漲了快10倍，錯過這趟快車甚是后悔，于是打算寫一個可不定期推...

xi4oh4o 2019-06-27 18:12 評論0 收藏0