零钱兑换

朴灿烈づ我的快乐病毒、 2022-12-04 09:58 162阅读 0赞

# 零钱兑换 #

## 1、参考资料 ##

https://leetcode-cn.com/problems/coin-change/

https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/bei-bao-ling-qian

## 2、题目要求 ##

> **题目描述**

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

> **示例 1:**

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

> **示例 2:**

输入: coins = [2], amount = 3
    输出: -1

> **说明**:

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

## 3、代码思路 ##

为什么可以使用动态规划？

我们的目标是求凑成总金额所需的最少的硬币个数，假如说我们现在已经选择了一块硬币，剩下的问题就是：我们如何找到凑出剩余金额的最少硬币数。这明摆着就是大问题与子问题的形式，我们用动态规划的 `dp` 数组存储子问题的结果，一步一步递推得到大问题的解

--------------------

转为完全背包问题

1.  硬币可以无限次放入 --> 不限制放入物品的个数，这不就是完全背包问题吗？但传统完全背包解决物品最大值的问题，本题我们是要解决最少硬币数数问题，其实也差不多
2.  我们将 `amount` 看做是背包容量，将硬币数量 `coins.length` 看做是物品数目，将 `coins` 看作是物品的重量，目标是求出填充满背包时，背包所能存放的最少硬币数
3.  既然动态规划需要将子问题的结果存储起来，那么我们定义 `dp[i][w]` 的含义为：对于前 `i` 个硬币(物品)，将其凑成 `w` 金额(填满容量为 `w` 的背包)所需的最少硬币数
4.  我们将不同的硬币一个一个放入背包中：`for (int i = 1; i <= N; i++) {`，对于每个硬币，我们一点一点增大目标金额(背包容量)：`for (int w = 1; w <= W; w++) {`，每次增加背包容量时，都尝试将第 `i` 个硬币放入背包中，将本次放入第 `i` 件物品与不放入第 `i` 件物品相比较，取硬币数少的方案
5.  由于需要求最小值，`dp[][]` 数组中的默认值不能为零，不然每次取最小值肯定都是 `0`，我们将 `dp[][0]` 初始化为 `0`，表示背包容量为零时，无法放入任何硬币；将 `dp[][]` 数组中的其他值初始化为 `amount + 1`，因为硬币数量最多为 `amout`，`amout+1` 是一个不可能的数字，假如说动态规划完成后 `dp[N][W] == (amount+1)`，则说明现有硬币无法拼凑出目标金额，返回 `-1` 表示拼凑失败，否则返回 `dp[N][W]`
6.  综上，状态转移方程为：`dp[i][w] = Math.min(dp[i][w - coins[i - 1]] + 1, dp[i - 1][w]);`

## 4、代码实现 ##

代码

class Solution {
        
        public int coinChange(int[] coins, int amount) {
        
    
            int W = amount; // 背包容量
            int N = coins.length; // 物品数量
            int[][] dp = new int[N + 1][W + 1]; // dp 数组
    
            // 默认填充 amount + 1
            for (int i = 0; i < dp.length; i++) {
        
                for (int j = 0; j < dp[0].length; j++) {
        
                    dp[i][j] = amount + 1;
                }
            }
    
            // dp[][0] 填充 0，表示背包容量为零时，无法放入任何硬币
            for (int i = 0; i < dp.length; i++) {
        
                dp[i][0] = 0;
            }
    
            // 将不同的硬币一个一个放入背包中
            for (int i = 1; i <= N; i++) {
        
                // 一点一点增大目标金额(背包容量)
                for (int w = 1; w <= W; w++) {
        
                    if (w < coins[i - 1]) {
        
                        // 如果不能放入背包，就取上次的最优解
                        dp[i][w] = dp[i - 1][w];
                    } else {
        
                        // 否则，可以放入背包，尝试将其放入背包，并取最优解
                        dp[i][w] = Math.min(dp[i][w - coins[i - 1]] + 1, dp[i - 1][w]);
                    }
                }
            }
    
            if (dp[N][W] == amount + 1) {
        
                return -1;
            } else {
        
                return dp[N][W];
            }
        }
    }

## 5、代码优化 ##

> **优化思路**

由于是完全背包问题，我们可以将 `dp` 数组优化为一维数组，对于当前第 `i` 个硬币，`dp[w]` 表示背包容量为 `w` 时，放入第 `i` 个硬币所需的最少硬币数

状态转移方程为：`dp[w] = Math.min(dp[w], dp[w - coins[i - 1]] + 1);`，对于第 `i` 个硬币，可选择放入或者不放入

> **代码实现**

class Solution {
        
            public int coinChange(int[] coins, int amount) {
        
                int W = amount; // 背包容量
                int N = coins.length; // 物品数量
                int[] dp = new int[W + 1]; // dp 数组
                Arrays.fill(dp, amount + 1); // 填充默认值：amount + 1
                dp[0] = 0; // 背包容量为零时，最少硬币数为零
                for (int i = 1; i <= N; i++) {
         // 遍历一件一件的物品
                    for (int w = 1; w <= W; w++) {
         // 从小到大增加背包容量
                        if (w >= coins[i - 1]) {
         // 如果能放下，则试着放
                            dp[w] = Math.min(dp[w], dp[w - coins[i - 1]] + 1);
                        }
                    }
                }
    
                if (dp[W] == amount + 1) {
        
                    return -1;
                } else {
        
                    return dp[W];
                }
            }
        }