使用「换元一维优化」方式求解完全背包

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的518. 零钱兑换 II，难度为 Medium。

给定不同面额的硬币和一个总金额。

写出函数来计算可以凑成总金额的硬币组合数。

假设每一种面额的硬币有无限个。

示例 1:

输入: amount = 5, coins = [1, 2, 5]

输出: 4

解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
复制代码

示例 2:

输入: amount = 3, coins = [2]

输出: 0

解释: 只用面额2的硬币不能凑成总金额3。
复制代码

示例 3:

输入: amount = 10, coins = [10] 

输出: 1
复制代码

注意:

你可以假设：

0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

完全背包（朴素解法）

在上一题 [322. 零钱兑换] 中，我们求的是「取得特定价值所需要的最小物品个数」。

对于本题，我们求的是「取得特定价值的方案数量」。

求的东西不一样，但问题的本质没有发生改变，同样属于「组合优化」问题。

你可以这样来理解什么是「组合问题」：

被选物品之间不需要满足特定关系，只需要选择物品，以达到「全局最优」或者「特定状态」即可。

同时硬币相当于我们的物品，每种硬币可以选择「无限次」，很自然的想到「完全背包」。

这时候可以将「完全背包」的状态定义搬过来进行“微调”：

定义 $f[i][j]$ 为考虑前 $i$ 件物品，凑成总和为 $j$ 的方案数量。

为了方便初始化，我们一般让 $f[0][x]$ 代表不考虑任何物品的情况。

因此我们有显而易见的初始化条件： $f[0][0] = 1$ ，其余 $f[0][x] = 0$ 。

代表当没有任何硬币的时候，存在凑成总和为 0 的方案数量为 1；凑成其他总和的方案不存在。

当「状态定义」与「基本初始化」有了之后，我们不失一般性的考虑 $f[i][j]$ 该如何转移。

对于第 $i$ 个硬币我们有两种决策方案：

不使用该硬币：

$f[i][j] = f[i – 1][j]$

使用该硬币：由于每个硬币可以被选择多次（容量允许的情况下），因此方案数量应当是选择「任意个」该硬币的方案总和：

$f[i][j] = \sum_{k = 1}^{\left \lfloor {j / val} \right \rfloor}f[i – 1][j – k * val], val = nums[i – 1]$

代码：

class Solution {
    public int change(int cnt, int[] cs) {
        int n = cs.length;
        int[][] f = new int[n + 1][cnt + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            for (int j = 0; j <= cnt; j++) {
                f[i][j] = f[i - 1][j];
                for (int k = 1; k * val <= j; k++) {
                    f[i][j] += f[i - 1][j - k * val];  
                }
            }
        }
        return f[n][cnt];
    }
}
复制代码

时间复杂度：共有 $n * cnt$ 个状态需要转移，每个状态转移最多遍历 $cnt$ 次。整体复杂度为 $O(n * cnt^2)$ 。
空间复杂度： $O(n * cnt)$ 。

完全背包（一维优化）

显然二维完全背包求解方案复杂度有点高。

$n$ 的数据范围为 $10^2$ ， $cnt$ 的数据范围为 $10^3$ ，总的计算量为 $10^8$ 以上，处于超时边缘（实际测试可通过）。

我们需要对其进行「降维优化」，可以使用最开始讲的数学分析方式，或者上一讲讲的换元优化方式进行降维优化。

由于数学分析方式十分耗时，我们用得更多的换元优化方式。两者同样具有「可推广」特性。

因为后者更为常用，所以我们再来回顾一下如何进行换元一维优化：

在二维解法的基础上，直接取消「物品维度」
确保「容量维度」的遍历顺序为「从小到大」（适用于「完全背包」）
将形如 $f[i – 1][j – k * val]$ 的式子更替为 $f[j – val]$ ，同时解决「数组越界」问题（将物品维度的遍历修改为从 $val$ 开始）

代码：

class Solution {
    public int change(int cnt, int[] cs) {
        int n = cs.length;
        int[] f = new int[cnt + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            for (int j = val; j <= cnt; j++) {
                f[j] += f[j - val];
            }
        }
        return f[cnt];
    }
}
复制代码