题目链接
题目描述
实现代码
动态规划思想:记dp[i]表示使用coins数组凑成i金额的最少兑换次数,因此有动态转移方程:
dp[i] = min(dp[i - coins[0], … dp[i-coins[n-1]) + 1
需要注意以下几点:
初始化条件:
dp[0] = 0; dp[coins[i]] = 1
不能兑换的判定(即值为-1的判定)
实现代码:
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
int len = coins.length;
for (int i = 1; i <= amount; i++) {
int min = Integer.MAX_VALUE;
boolean can = false;
for (int j = 0; j < len; j++) {
if (i < coins[j]) {
continue;
}
if (i == coins[j]) {
min = 0;
can = true;
break;
}
if (dp[i - coins[j]] == -1) {
continue;
}
if (min > dp[i - coins[j]]) {
min = dp[i - coins[j]];
can = true;
}
}
dp[i] = can ? min + 1 : -1;
}
return dp[amount];
}
}