详解完全背包一维空间优化推导（附背包问题攻略）

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

题目描述

这是 LeetCode 上的 279. 完全平方数 ，难度为 中等。

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

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
复制代码

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9
复制代码

提示：

• 1 <= n <= $10^4$

完全背包（朴素解法）

首先「完全平方数」有无限个，但要凑成的数字是给定的。

因此第一步可以将范围在 $[1, n]$ 内的「完全平方数」预处理出来。

这一步其实就是把所有可能用到的「物品」预处理出来。

从而将问题转换为：给定了若干个数字，每个数字可以被使用无限次，求凑出目标值 $n$ 所需要用到的是最少数字个数是多少。

由于题目没有限制我们相同的「完全平方数」只能使用一次，属于「完全背包」模型。

目前我们学过的两类背包问题（01 背包 & 完全背包）的原始状态定义都是两维：

• 第一维 $i$ 代表物品编号

• 第二维 $j$ 代表容量

其中第二维 $j$ 又有「不超过容量 $j$」和「容量恰好为 $j$」两种定义，本题要我们求「恰好」凑出 $n$ 所需要的最少个数。

因此我们可以调整我们的「状态定义」：

$f[i][j]$ 为考虑前 $i$ 个数字，凑出数字总和 $j$ 所需要用到的最少数字数量。

不失一般性的分析 $f[i][j]$，对于第 $i$ 个数字（假设数值为 $t$），我们有如下选择：

• 选 $0$ 个数字 $i$，此时有 $f[i][j] = f[i – 1][j]$
• 选 $1$ 个数字 $i$，此时有 $f[i][j] = f[i – 1][j – t] + 1$
• 选 $2$ 个数字 $i$，此时有 $f[i][j] = f[i – 1][j – 2 * t] + 2$
  …
• 选 $k$ 个数字 $i$，此时有 $f[i][j] = f[i – 1][j – k * t] + k$

因此我们的状态转移方程为：