⭐️【一维优化强化以及无效状态】零钱兑换⭐️

🔐题目详情

322. 零钱兑换

难度中等

给你一个整数数组 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

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

💡解题思路与代码

🍭朴素解法

首先我们来分析一下题目，题目给了我们很多硬币有各种面值，每种硬币可以选择无数次，需要求这些硬币和恰好为amount的最小所选硬币数。

这里我们可以将每一种硬币视为一种【物品】，amount可以视为背包的容量，硬币的面值可以看做物品的【体积】，所用的硬币数我们可以理解为【总价值】，则每种硬币的【价值】就是1，这样我们就能够将这个问题视作我完全背包问题。

状态定义： 不妨定义 $f[i][j]$表示从前 $i$种硬币中选择，恰好凑成 $j$，所选物品的最小数量，由于硬币的面值是不定的，所以可能选择若干硬币可能凑不出amount，所以我们需要定义一个无效值来表示这个状态是无效的，也就是无法凑出amount的，由于我们求的是最小的硬币数，所以我们选择的无效值要比较大，可以选择Integer.MAX_VALUE。

确定初始状态： 当 $i=0$时，只能选择第一个硬币，那么就尽量选，能凑成 $j$，就加上所选的硬币个数，否则就将该状态赋值为无效值。

状态转移方程推导： 当我们选择第 $i$种硬币的时候，我们可以选择 $0,1,2...k$枚，其中 $k$是最大能够选择的硬币数，即在恰好凑出 $j$的情况下。
假设第 $i$件硬币的数值【体积】为 $t$。
当我们不选择第 $i$件硬币时，即 $k=0$， $f[i][j]=f[i-1][j]$。
当我们选择 $1$件第 $i$件硬币时，即 $k=1$， $f[i][j]=f[i-1][j - t] + 1$。
当我们选择 $2$件第 $i$件硬币时，即 $k=2$， $f[i][j]=f[i-1][j - 2 * t] + 2$。
…
当我们选择 $k$件第 $i$件硬币时，即 $k=k$， $f[i][j]=f[i-1][j - k * t]+k$。

我们所要求的是最小的硬币数量，所以取以上所有情况的最小值即可。

综上所述，我们的状态转移方程就出来了，当能够凑出 $j$时，不妨记当前所选硬币的数量为：

$$f[i][j]=min(f[i-1][j-k*t]+k),k=0,1,...$$

但是选择 $k$个硬币还是无法凑出` $j$时，该状态为无效值：

$$f[i][j]=INF$$

实现代码：

class Solution {
    //无效值
    private int INF = 0x3f3f3f;
    public int coinChange(int[] coins, int amount) {
        //获取硬币的个数
        int n = coins.length;

        int[][] f = new int[n][amount + 1];

        //确定初始状态
        for (int j = 1; j <= amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] != j) f[0][j] = INF;
            else f[0][j] = k;
        }

        //状态转移
        for (int i = 1; i < n; i++) {
            int t = coins[i];
            for (int j = 0; j <= amount; j++) {
                //不选
                f[i][j] = f[i - 1][j];
                // 选k个
                for (int k = 1; j >= k * t; k++) {
                    if (f[i - 1][j - k * t] != INF) {
                        f[i][j] = Math.min(f[i][j], f[i - 1][j - k * t] + k);
                    }
                }
            }
        }
        return f[n - 1][amount] == INF ? -1 : f[n - 1][amount];
    }
}

时间复杂度： $O(amount^2*n)$， $k$的值不会大于 $amount$，因为 $t$最小为 $1$，最多选择的数的数量不会超过 $amount$。
空间复杂度： $O(n*amount)$

🍭滚动数组优化空间

根据观察我们知道第 $i$行的状态仅依赖与第 $i-1$行的状态，因此我们可以使用滚动数组进行优化。

实现代码：

class Solution {
    //无效值
    private int INF = 0x3f3f3f;
    public int coinChange(int[] coins, int amount) {
        //
        int n = coins.length;

        int[][] f = new int[2][amount + 1];

        //确定初始状态
        for (int j = 1; j <= amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] != j) f[0][j] = INF;
            else f[0][j] = k;
        }

        //状态转移
        for (int i = 1; i < n; i++) {
            int t = coins[i];
            int pre = (i - 1) & 1;
            int cur = i & 1;
            for (int j = 0; j <= amount; j++) {
                //不选
                f[cur][j] = f[pre][j];
                // 选k个
                for (int k = 1; j >= k * t; k++) {
                    if (f[pre][j - k * t] != INF) {
                        f[cur][j] = Math.min(f[cur][j], f[pre][j - k * t] + k);
                    }
                }
            }
        }
        return f[(n - 1) & 1][amount] == INF ? -1 : f[(n - 1) & 1][amount];
    }
}

对于时空复杂度，只是优化了空间而已，所以时间复杂度不发生改变，空间复杂度优化到 $O(amount)$。
时间复杂度： $O(amount^2*n)$， $k$的值不会大于 $amount$，因为 $t$最小为 $1$，最多选择的数的数量不会超过 $amount$。
空间复杂度： $O(amount)$

🍭一维数组优化空间

首先我们对状态转移方程进行一个简单的推导：

$$f[i][j]=min(f[i-1][j],f[i-1][j-t]+1,f[i-1][j-2*t]+2,...,f[i-1][j-kt]+k)$$

$$f[i][j-t]=min(f[i-1][j-t],f[i-1][j-2t]+1,f[i-1][j-3t]+2...,f[i-1][j-kt]+k-1)$$

其中 $k*t<=j$。

通过观察上面两个状态的式子，我们发现后面一部分式子是差了一个 $1$如下图：

所以我们可以进一步优化状态转移方程，即：

$$f[i][j]=min(f[i-1][j],f[i][j-t]+1)$$

对于新推导出来的状态转移方程，它的状态转移仅仅只依赖与上一行同列状态与同一行元素前面的元素，所以我们可以将原来的二维数组优化为一维，由于它只依赖左边与正上方的元素，我们可以采取从小到大遍历背包容量状态来求背包中所放物品最大值。

只保留【凑出amount】维度，状态转移方程为：

$$f[j]=max(f[j],f[j-t]+1)$$

前面我们定义了一个INF，取值为整型的最大值，其实我们可以预留一些空间，就是取一个比最大值小一点的数，这样在就给了这个无效值累加的空间，不会出现越界变为负数的问题，这样我们就可以不用在进行判断前一个依赖的状态是否是INF。

实现代码：

class Solution {
    private static final int INF = 0x3f3f3f3f;
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;

        int[] f = new int[amount + 1];

        //确定初始状态
        for (int j = 1; j <= amount; j++) {
            int k = j / coins[0];
            if (k * coins[0] != j) f[j] = INF;
            else f[j] = k;
        }

        for (int i = 0; i < n; i++) {
            int t = coins[i];
            for (int j = t; j <= amount; j++) {
                f[j] = Math.min(f[j], f[j - t] + 1);
            }
        }
        return f[amount] == INF ? -1 : f[amount];
    }
}

时间复杂度： $O(amount*n)$
空间复杂度： $O(amount+1)$

🌱总结

本篇文章介绍了【完全背包】的运用，使用该模型运用到实际的问题当中，强化一维优化过程的推导。

对于完全背包的优化，相比于0-1背包问题的优化，形式上，我们只需要将 01 背包问题的「一维空间优化」解法中的「容量维度」遍历方向从「从大到小 改为 从小到大」就可以解决完全背包问题。
但本质是因为两者进行状态转移时依赖了不同的格子：
0 -1 背包依赖的是「上一行正上方的格子」和「上一行左边的格子」。
完全背包依赖的是「上一行正上方的格子」和「本行左边的格子」。

参考资料： 宫水三叶背包问题