322、零钱兑换
基本思想:
每种硬币的数量是无限的------完全背包
与518题不同,518问的是方法种类,本题问的是硬币个数
具体实现:
1.确定dp数组以及下标的含义
dp[j]:凑足总额为j所需钱币的最少个数为dp[j]
2.确定递推公式
完全背包公式:
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题:dp[j] = min(dp[j],dp[j - coins[i]] + 1);
对应到背包问题上硬币面值是物品重量,一个硬币的数量对应物品价值
3.dp数组初始化
凑足总金额为0所需钱币的个数一定是0,那么dp[0] = 0;
考虑到递推公式的特性,dp[j]必须初始化为一个最大的数,否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。
所以下标非0的元素都是应该是最大值。
4.确定遍历顺序
本题的两个for循环的关系是:外层for循环遍历物品,内层for遍历背包或者外层for遍历背包,内层for循环遍历物品都是可以的
从前向后
5.举例
代码:
class Solution { public int coinChange(int[] coins, int amount) { int max = Integer.MAX_VALUE; int[] dp = new int[amount + 1]; for (int j = 1; j < dp.length; j++){ dp[j] = max; } dp[0] = 0; for (int i = 0; i < coins.length; i++){ for (int j = coins[i]; j <= amount; j++){ if (dp[j - coins[i]] != max){ dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1); } } } return dp[amount] == max ? -1:dp[amount]; } }