Code Casual Recording Notes_Dynamic Programming_322 Change Exchange

代码随想录二刷笔记记录

LC322.零钱兑换

题目

完全背包

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额.

计算并返回可以凑成总金额所需的 最少的硬币个数 .如果没有任何一种硬币组合can make up the total 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

思路分析

与 LC 528 不同,This question does not ask for the number of combinations,Instead, find the minimum number of coins,因此,我们可知,This question does not require traversal order.

思路：
1.硬币有无限个

2.Find the minimum number of coins to make up the total amount

从条件1可知,本题是一个完全背包问题.

总金额 = 背包容量,硬币 = 物品, 每种硬币的数量无限：完全背包问题

动态规划五部曲

1.确定dp数组及其下标的含义

dp[j]：can make up the total amount j 的最少硬币个数
即：The minimum items to fill a backpack

2.确定递推公式

能推导出 dp[j] 的上一步为 dp[j - coin[i]]
凑成总金额 j - coin[i] The minimum number of coins is  dp[j - coin[i]],此时加上一个coin[i],即 dp[j] = dp[j - coin[i]] + 1
由于 dp[j - coin[i]] 有很多个状态,因此,dp[j] 取所有dp[j - coin[i]] 中最小的.
递推公式：dp[j] = Min(dp[j], dp[j - coin[i]] + 1)

3.初始化

凑成总金额为 0 所需的 coin 个数为 0 ,因此 dp[0] = 0.And because of the characteristic of recursive formula to find the minimum value,Other subscripts should be initialized to the maximum value Integer_Max , 否则,Due to the recursive formula and Min 函数的特点,will be overwritten by the initial value0.

4.遍历顺序

This question can first traverse the backpack or items,没有特别要求

for(int i = 0;i < coins.length(); i++){
     // 物品
	for(int j = coins[i];j <= amount;j++){
     // 背包
    	dp[j] = Min(dp[j],dp[j - coins[i]] + 1)
	}
}

5.推演分析

以 coins[1,2,5] . amount = 5 为例

maxValue = Integer_Max

代码实现

完整代码实现

public static int coinChange(int[] coins, int amount) {
    
        //初始化
        int[] dp = new int[amount+1];
        for (int i = 0;i < dp.length;i++){
    
            dp[i] = Integer.MAX_VALUE;
        }
        //总金额为0时,The number of coins is0
        dp[0] = 0;
        //遍历顺序
        for(int i = 0;i < coins.length;i++){
     // 遍历物品
            for(int j = coins[i];j <= amount;j++){
    //遍历背包容量
                // If the previous state dp [j - coin[i]] 为最大值,It means that the status has not changed
                // So no changes are needed here either
                if(dp[j - coins[i]] != Integer.MAX_VALUE)
                    dp[j] = Math.min(dp[j],dp[j - coins[i]] + 1);
                System.out.print(dp[j] + " ");
            }
            System.out.println();
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }