Coin Change 2
给一个amount给一个coin数组, 问从coin中组成amount的多少种可能. 这个是典型的dp题, 设dp[i]是i块钱的找零个数. 那么我们就可以推断出, dp[i] += dp[i-coin[j]], 但是dp的初始值怎么设计? 我们设dp[0] = 1, 这意味着当, 当前的coin的和等于amount的时候, 算作一种找零方法.
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount+1];
dp[0] = 1;
for(int i = 0 ; i < coins.length; i++) {
for(int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}