代码随想录动态规划——零钱兑换_零钱兑换算法

题目

给定不同面额的硬币 coins 和一个总金额amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1： 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

示例 2： 输入：coins = [2], amount = 3 输出：-1

示例 3： 输入：coins = [1], amount = 0 输出：0

示例 4： 输入：coins = [1], amount = 1 输出：1

示例 5： 输入：coins = [1], amount = 2 输出：2

提示：

1 <= coins.length <= 12 1 <= coins[i] <= 2^31 - 1 0 <= amount <= 10^4

思路

题目说每种硬币数量是无限的->完全背包问题

动规五部曲：

1. 确定dp数组以及下标的含义
   dp[i]表示凑成总金额为 i 所需要的最少钱币数为dp[i]

2. 确定递推公式
   对于第j个硬币coins[j],可以选或者不选，考虑 coins[j]得到dp[i]，不考虑coins[j]为dp[i - coins[j]]，即dp[i]只有一个来源dp[i - coins[j]]（在没有考虑coins的情况下）
   凑成总金额为i - coins[j]的最少个数为dp[i - coins[j]]，那么只需要加上一个钱币coins[j]即dp[i - coins[j]] + 1就是dp[i]
   所以dp[i]要取所有dp[i - coins[j]] + 1 中最小的，即
   dp[i] = min(dp[i - coins[j]] + 1, dp[i])

3. dp数组初始化
   dp[0] =0，表示凑足总金额为0的钱币个数为0个，而其他下标的初始值应该设为最大值，因为考虑递推公式要取最小值，所以dp[i]要初始化为一个最大的数，否则就会在递推min(dp[i - coins[j]] + 1, dp[i])中被初始值覆盖

4. 确定遍历顺序
   本题求钱币最小数量，并未强调是组合还是排序，所以两个for循环没有先后顺序

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
1
2

5. 举例推导dp数组
   以输入：coins = [1, 2, 5], amount = 5为例
   
   java代码如下：

class Solution {
	public int coinChange(int[] coins, int amount){
		int max = Integer.MAX_VALUE;
		int[] dp = new int[amount + 1];
		for(int i = 0; i < dp.length; i++){
			dp[i] = max;
		}
		dp[0] = 0;
		for(int i = 1; i <= amount; i++){//先遍历背包容量
			for(int j = 0; j < coins.length; j++){//再遍历物品
				if(coins[j] <= i && dp[i - coins[j]]!= max){//只要物品的大小小于背包的容量，就进行判断,同时前提是dp[i-coins[j]]必须有值，如果dp[i-coins[j]]是无穷大，说明无法凑出i-coins[j]价值的钱包,进而也凑不出dp[i]的值
					dp[i] = Math.min(dp[i- coins[j]] + 1,dp[i]);
				} 
			}
		}
		return dp[amount] == max ? -1 : dp[amount];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18