详解完全背包问题

这是我参与更文挑战的第 10 天，活动详情查看：更文挑战

题目描述

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

Tag : 「背包问题」、「完全背包」、「动态规划」

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。 

示例 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$ 个硬币我们有两种决策方案：

• 不使用该硬币：