[LeetCode] 322. Coin Change

ccj659 發布于2019-08-16 13:37 / 3241人閱讀

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 of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.

Solution

class Solution {
    public int coinChange(int[] coins, int n) {
        if (n < 1) return 0;
        int[] dp = new int[n+1]; 
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= n; i++) {
                if (dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i-coin] + 1);
                }
            }
        }
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
}

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72037.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 - 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