題目：
給定一串零錢面額和需要找的零錢數(shù)。求需要找的零錢數(shù)量的最小值。
舉例：
零錢面額：1涧至，2，5桑包，21南蓬，25
零錢數(shù)：63
結(jié)果：3（21*3）
思路：
此題可以使用動態(tài)規(guī)劃的思想求解。首先需要明確動態(tài)規(guī)劃的數(shù)組的意義，dp[i]代表著當(dāng)零錢數(shù)為i的時候需要找的最小零錢數(shù)是多少赘方。其次是狀態(tài)方程：
dp[i] = Math.min(dp[i], dp[j] + dp[i - j])
Note：j是小于i的任意一個數(shù)烧颖，該方程的意義是找出當(dāng)前已知的零錢最少數(shù)和未知的零錢最少數(shù)誰最小。
首先需要創(chuàng)建一個dp數(shù)組初始值設(shè)為零窄陡，存在于零錢數(shù)組中的數(shù)設(shè)為1炕淮。之后動態(tài)規(guī)劃進(jìn)行查找，查找出給定的零錢數(shù)i之前所有零錢的最小值直到最后的i跳夭。
Note：動態(tài)規(guī)劃的過程中需要判斷dp[i]是否為零涂圆，如果為零，則將dp[j] + dp[i - j]賦給dp[i]币叹。
代碼：
/**
* Find the minimal number of coins.
* @param coins
* @param amount
* @return
*/
public int solution(int [] coins, int amount){
if(coins == null || coins.length == 0 || amount == 0)
return 0;
int length = amount > coins[coins.length - 1] ? amount : coins[coins.length - 1];
int [] dp = new int [length + 1];
for(int i = 0;i<coins.length;i++){
dp[coins[i]] = 1;
}
for(int i=1;i<=amount;i++){
for(int j=0;j<i;j++){
if(dp[i] == 0){
dp[i] = dp[j] + dp[i-j];
}else{
dp[i] = Math.min(dp[j] + dp[i-j], dp[i]);
}
}
}
return dp[amount];
}
