思路
- dp问题，空间换时间，递推公式(初始化+转移方程),
F(S) = F(S-C) + 1
# S 代表总额(amount), F(S)代表最少兑换次数，C代表兑换的最后一个面值，其中 S为0时，F(S) = 0, 零钱数组为空时，F(S)=-1.
解法
public int coinChange(int[] coins, int amount) {
return coinChange(0, coins, amount);
}
private int coinChange(int coinsIndex, int[] coins, int amount) {
if (amount == 0) {
return 0;
}
if (coinsIndex == coins.length) {
return -1;
}
int min = Integer.MAX_VALUE;
int maxNum = amount / coins[coinsIndex];
for (int num = 0; num <= maxNum; num++) {
int otherNums = coinChange(coinsIndex + 1, coins, amount - num * coins[coinsIndex]);
if(otherNums != -1) {
min = Math.min(min, otherNums + num);
}
}
return min == Integer.MAX_VALUE ? -1 : min;
}
public int coinChange(int[] coins, int amount) {
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int amount, int[] nums) {
if (amount == 0) {
return 0;
}
if (amount < 0) {
return -1;
}
if (nums[amount-1] != 0) return nums[amount-1];
int min = Integer.MAX_VALUE;
for (int lastCoin : coins) {
int res = coinChange(coins, amount - lastCoin, nums);
if (res >= 0 && res < min) {
min = res + 1;
}
}
nums[amount-1] = (min == Integer.MAX_VALUE) ? -1 : min;
return nums[amount-1];
}
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int lastCoin : coins) {
if (i >= lastCoin) {
dp[i] = Math.min(dp[i], dp[i - lastCoin] + 1);
}
}
}
if (dp[amount] == amount + 1) {
return -1;
}
return dp[amount];
}