Coin Change 2
给一个amount给一个coin数组, 问从coin中组成amount的多少种可能. 这个是典型的dp题, 设dp[i]是i块钱的找零个数. 那么我们就可以推断出, dp[i] += dp[i-coin[j]], 但是dp的初始值怎么设计? 我们设dp[0] = 1, 这意味着当, 当前的coin的和等于amount的时候, 算作一种找零方法.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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]; } } |