动态规划既找子问题,由子问题递推大问题.
拆分coins =[1, 2, 5],amount=11,那么面值为11的最小可能和为以下可能的最小值:
我们 设dp[amount]为金额为amount的最小可能组合 这里dp[11]=min(1+dp[11-coins[0],1+coins[11-coins[1],1+coins[11-coins[2])
即dp[amount] = min(dp[amount], 1 + dp[amount - coins[i]]) for i in [0, len - 1] if coins[i] <= amount
同时我们要知道和注意:
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
//这里我们要求最小组合数,因此这里可以填充最大值
Arrays.fill(dp, Integer.MAX_VALUE);
//0元的组合必然啥都么有
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
//遍历每种可能
for (int coin : coins) {
//1. i - coin >= 0 意思当前硬币要小于等于我们要凑的钱数,另外要凑的子金额要大于0;
//2. dp[i - coin] != Integer.MAX_VALUE 意思我们剩下的钱也是要能凑齐的才行;
// 不是所有的dp都有意义,有可能这个组合就是不存在,因此这里也可以理解为只有除掉不可拆分的硬币之外剩余的钱必须能被凑齐才有意义做为比较值;
if (i - coin >= 0 && dp[i - coin] != Integer.MAX_VALUE) {
dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
}
}
}
return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}
}