[LeetCode] 518. Coin Change 2

stefan 發(fā)布于2019-08-16 13:44 / 1415人閱讀

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);
        }
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/72246.html

相關(guān)文章

leetcode322. Coin Change

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

kohoh_ 2019-08-15 14:41 評(píng)論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 評(píng)論0 收藏0
[LeetCode - Dynamic Programming] Coin Change

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

dackel 2019-08-16 10:26 評(píng)論0 收藏0
100塊錢換零錢，最多有多少種方式的 JavaScript 版本實(shí)現(xiàn)

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

xeblog 2019-08-22 10:49 評(píng)論0 收藏0
koa2開發(fā)微信公眾號(hào): 不定期推送最新幣圈消息

摘要：背景比特幣說(shuō)好的分叉最后卻分叉不成，如今算力又不夠，于是比特現(xiàn)金想篡位沒(méi)一個(gè)星期就漲了快倍，錯(cuò)過(guò)這趟快車甚是后悔，于是打算寫一個(gè)可不定期推送最新消息的微信公眾號(hào)。既然是利用微信這個(gè)平臺(tái)載體，當(dāng)然要熟悉微信的，遂封裝了一下。背景：比特幣說(shuō)好的segwit2x分叉最后卻分叉不成，如今算力又不夠，于是比特現(xiàn)金想篡位? 沒(méi)一個(gè)星期就漲了快10倍，錯(cuò)過(guò)這趟快車甚是后悔，于是打算寫一個(gè)可不定期推...

xi4oh4o 2019-06-27 18:12 評(píng)論0 收藏0