[LeetCode - Dynamic Programming] Coin Change

dackel 發(fā)布于2019-08-16 10:26 / 2835人閱讀

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

Coin Change
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.

1.解題思路
動態(tài)規(guī)劃，用dp[i]表示總價為i的最小紙幣張數(shù)，很容易想到狀態(tài)轉移方程:
dp[i]=Math.min(dp[i-coins[0]]+1,dp[i-coins[1]]+1,...,dp[i-coins[n-1]]+1),當然前提是i要大于紙幣金額數(shù)。
dp[i-coins[0]]+1: 表示取一張coins[0]面額加上合計為i-coins[0]的最小紙幣數(shù)。
另題目要求無法合計出的金額i，dp[i]要返回-1，所以要作特殊處理，否則就會返回元素初始化值0.

2.代碼

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins.length==0) return -1;
        if(amount==0) return 0;
        int[] dp=new int[amount+1]; //start from 1, intead of 0
        for(int i=1;i<=amount;i++){
            int minNumber=Integer.MAX_VALUE;
            for(int j=0;j=coins[j]&&dp[i-coins[j]]!=-1){
                    minNumber=Math.min(dp[i-coins[j]]+1,minNumber);
                }
            }
            dp[i]=minNumber==Integer.MAX_VALUE?-1:minNumber;
        }
        return dp[amount];
    }
}

GPU云服務器云服務器 dynamic-programming Coin coin 域名行情 change

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

轉載請注明本文地址：http://systransis.cn/yun/69795.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_ 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] 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-Dynamic Programming]Unique Binary Search

Unique Binary Search TreesGiven n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BSTs. 1 3 3 ...

MartinDai 2019-08-16 10:27 評論0 收藏0
[Leetcode- Dynamic Programming] Best Time to Buy a

摘要：代碼解體思路依然是動態(tài)規(guī)劃，尋找狀態(tài)，因為本題涉及到，所以第天的狀態(tài)我們分為持股和未持股，即維護兩個數(shù)組，和分別表示第天持股和未持股所獲得的最大收益。 Best Time to Buy and Sell Stock Say you have an array for which the ith element is the price of a given stock on day...

hiyayiji 2019-08-14 16:41 評論0 收藏0