[LeetCode - Dynamic Programming] Coin Change

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

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

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