解题思路：
动态规划入门题。
详情可见：https://leetcode-cn.com/problems/coin-change/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-wei-lai-bu-ke/
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19java:
public int coinChange(int[] coins, int amount) {
int n = coins.length;
if(n == 0) return -1;
int[] dp = new int[amount+1];
//base case
dp[0] = 0;
for(int i = 1;i<=amount;++i){
int min = Integer.MAX_VALUE;
for(int j = 0;j<n;j++){
if(i - coins[j] >= 0 && dp[i - coins[j]] < min)
min = dp[i - coins[j]] + 1;
}
dp[i] = min;
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
