成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[LeetCode] 322. Coin Change

ccj659 / 3249人閱讀

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

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

轉載請注明本文地址:http://systransis.cn/yun/72037.html

相關文章

  • leetcode322. Coin Change

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

    kohoh_ 評論0 收藏0
  • [LeetCode - Dynamic Programming] Coin Change

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

    dackel 評論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 評論0 收藏0
  • LeetCode 精選TOP面試題【51 ~ 100】

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

    Clect 評論0 收藏0
  • 100塊錢換零錢,最多有多少種方式的 JavaScript 版本實現(xiàn)

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

    xeblog 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<