动态规划入门：斐波那契数与零钱兑换
动态规划经常用来解决具有重复子问题的题目。
一开始，我们可能会直接使用递归，将原问题拆成更小的子问题。但如果不同的递归分支反复计算相同的结果，就会浪费大量时间。
这时可以考虑使用备忘录，将已经计算过的结果保存下来，避免重复求解。
进一步思考，如果能够确定各个状态之间的依赖关系，还可以改成自底向上的迭代写法。
下面通过两道 LeetCode 题目，分别记录这几种实现方式。
1. LeetCode 509. 斐波那契数
斐波那契数列从 0 和 1 开始，后面的每一项都等于前两项之和。
其递推关系为：
其中，fib(0) = 0，fib(1) = 1。
1.1 朴素递归
根据斐波那契数列的定义，最容易想到的就是递归。
要求 fib(n)，只需要分别计算 fib(n - 1) 和 fib(n - 2)，再将它们相加。
对于 n = 0、1、2，可以直接返回对应的结果，作为递归的终止条件。
Python 代码：
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return 1
return self.fib(n - 1) + self.fib(n - 2)这种写法很直观，基本就是把数学定义翻译成了代码。
但它有一个明显的问题：递归过程中会反复计算相同的子问题。
例如，计算 fib(5) 时，需要分别计算 fib(4) 和 fib(3)。
而在计算 fib(4) 时，又需要计算 fib(3) 和 fib(2)。
fib(5)
/ \
fib(4) fib(3)
/ \
fib(3) fib(2)可以看到，fib(3) 被重复计算了。
随着 n 增大，这类重复计算会越来越多，朴素递归的时间复杂度可以用 表示。
问题不在于每次递归计算有多复杂，而在于同一个状态被反复求解。
1.2 备忘录优化：自顶向下
既然重复计算浪费时间，那么能不能把已经计算过的结果保存下来，下次需要时直接使用？
这就是备忘录的思路，也叫记忆化搜索。
我们可以创建一个 memo 数组，用来记录各个 fib(n) 的计算结果。
每次进入递归函数时：
- 如果遇到基础状态，直接返回对应结果。
- 检查备忘录中是否已经保存当前状态。
- 如果已经计算过，就直接返回保存的结果。
- 如果还没有计算，就继续递归，并将得到的结果存入备忘录。
这样就不需要每次都重新展开同一棵递归子树。
Python 代码：
class Solution:
def fib(self, n: int) -> int:
memo = [-1 for _ in range(n + 1)]
return self.func(n, memo)
def func(self, n, memo):
if n == 0:
return 0
elif n == 1:
return 1
elif n == 2:
return 1
if memo[n] != -1:
return memo[n]
memo[n] = self.func(n - 1, memo) + self.func(n - 2, memo)
return memo[n]这里使用 -1 表示某个状态还没有被计算过。
因为斐波那契数不会出现负数，所以可以安全地使用这个值作为标记。
和朴素递归相比，记忆化搜索不再反复计算相同的非基础状态，时间复杂度降低到了 。
不过，这种写法仍然使用递归，而且还需要额外创建一个长度为 n + 1 的备忘录数组，因此空间复杂度为 。
这种从目标问题开始，逐步向下分解并保存结果的方式，就是自顶向下的动态规划。
1.3 自底向上：迭代实现
除了使用递归，我们还可以反过来思考。
既然已经知道：
而且每一项都可以通过前两项计算出来，那么完全可以从最基础的状态开始，依次计算后面的结果。
例如：
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5这种方式就是自底向上的动态规划。
进一步观察可以发现，计算 fib(n) 时，只需要知道前两个状态的值。
因此，没必要保存从 fib(0) 到 fib(n) 的所有结果，只需要使用两个变量记录前两项，并在每轮循环中更新即可。
Python 代码：
class Solution:
def fib(self, n: int) -> int:
if n < 2:
return n
fib_n_1 = 1
fib_n_2 = 0
fib_n = 0
for i in range(2, n + 1):
fib_n = fib_n_1 + fib_n_2
fib_n_2 = fib_n_1
fib_n_1 = fib_n
return fib_n其中：
fib_n_1保存前一项的值。fib_n_2保存前两项的值。fib_n用来计算当前项。
每次计算出新的斐波那契数后，再更新前两个变量，为下一轮循环做准备。
这样既避免了递归中的重复计算，也不需要额外维护整个备忘录数组。
最终时间复杂度仍然为 ，但额外空间复杂度降低到了 。
通过这道题，可以看到三种写法之间的关系：
| 解法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 朴素递归 | ||
| 递归 + 备忘录 | ||
| 迭代 + 两个变量 |
这也是动态规划中比较常见的优化过程：先通过递归找到状态之间的关系，再用备忘录消除重复计算，最后根据状态依赖关系考虑能否改成迭代，甚至进一步压缩空间。
2. LeetCode 322. 零钱兑换
这道题给出了若干种不同面额的硬币，以及一个目标金额 amount。
每种硬币可以使用任意多次，要求计算凑出目标金额需要的最少硬币数量。如果无法凑出，则返回 -1。
例如：
coins = [1, 2, 5]
amount = 11
答案：3因为可以使用两枚面额为 5 的硬币，再加上一枚面额为 1 的硬币，刚好凑出 11，一共需要 3 枚。
2.1 分解子问题
这道题也可以先从递归的角度考虑。
假设我们现在需要凑出金额 amount，那么每次都可以从 coins 中选择一枚硬币。
选择之后，剩余需要凑出的金额就是：
amount - coin
例如，当 coins = [1, 2, 5]、amount = 11 时：
- 选择面额
1，剩余金额为10。 - 选择面额
2，剩余金额为9。 - 选择面额
5，剩余金额为6。
假设凑出这三个剩余金额需要的最少硬币数分别为 x、y、z，那么凑出金额 11 所需的最少硬币数就是：
这里加上的 1，就是本次选择的那枚硬币。
当然，如果某种选择无法凑出剩余金额，就不能把它计入最小值的比较。
因此，我们可以定义：
dp(amount) 表示凑出指定金额所需的最少硬币数量。
对于每种硬币，分别递归计算剩余金额的最优结果，再从所有可行选择中取最小值。
对应的状态转移关系可以写成：
如果没有任何可行的选择，就说明当前金额无法凑出。
2.2 递归的终止条件
在实现之前，还需要考虑递归什么时候结束。
这里有两种情况：
第一种：amount == 0
说明目标金额已经凑齐，不需要再选择硬币，因此返回 0。
第二种：amount < 0
说明当前选择的硬币面额超过了剩余金额，这条递归路径不可行，因此返回 -1。
另外，这道题同样存在重复子问题。
例如，凑金额 11 时，不同的硬币选择顺序可能都会遇到“还需要凑出金额 6”这样的状态。
如果每次都重新计算，就会产生大量重复递归。
因此，可以沿用第 509 题的思路，通过备忘录保存每个剩余金额的计算结果。
2.3 备忘录实现
Python 代码：
class Solution:
def __init__(self):
self.memo = []
def coinChange(self, coins: List[int], amount: int) -> int:
self.memo = [-666] * (amount + 1)
return self.dp(coins, amount)
def dp(self, coins, amount):
if amount == 0:
return 0
if amount < 0:
return -1
if self.memo[amount] != -666:
return self.memo[amount]
res = float("inf")
for coin in coins:
subProblem = self.dp(coins, amount - coin)
if subProblem == -1:
continue
res = min(res, subProblem + 1)
self.memo[amount] = res if res != float("inf") else -1
return self.memo[amount]这里的备忘录使用 -666 表示某个金额还没有被计算过。
而 -1 表示已经计算过，但无法凑出这个金额。两者的含义不同，所以不能混用。
在 dp() 函数中，先将 res 初始化为正无穷：
res = float("inf")然后遍历所有硬币，尝试计算选择当前硬币后的子问题。
如果子问题返回 -1，说明当前选择不可行，直接跳过。
否则就使用：
res = min(res, subProblem + 1)不断更新最少硬币数量。
如果尝试完所有面额后，res 仍然是正无穷，就说明没有任何可行方案，应当返回 -1。
最后，将结果保存到备忘录中。下次遇到相同的金额时，就可以直接返回，不需要再次展开递归。
2.4 自底向上：使用 DP 数组
和斐波那契数一样，零钱兑换也可以改成迭代写法。
既然已经知道凑出金额 0 不需要任何硬币，那么就可以从 0 开始，依次计算凑出金额 1、2、3……所需要的最少硬币数。
这里使用一个 dp 数组：
dp[i] 表示凑出金额 i 所需要的最少硬币数量。
每次计算 dp[i] 时，依次尝试所有硬币。
如果选择了面额为 coin 的硬币，那么剩余金额就是 i - coin。
只要 i - coin >= 0，就可以尝试通过下面的关系更新答案：
其中的 +1，同样表示本次选择的硬币。
2.5 初始化 DP 数组
这里有一个值得注意的细节：DP 数组的初始值。
我们可以先将所有位置初始化为 amount + 1：
dp = [amount + 1] * (amount + 1)这是因为题目中的硬币面额都是正整数。如果一个金额能够被凑出来，那么即使全部使用面额为 1 的硬币，所需数量也不会超过目标金额本身。
因此，amount + 1 可以用来表示一个暂时无法凑出的状态。
接着，将：
dp[0] = 0表示凑出金额 0 不需要任何硬币。
之后从小到大枚举金额，每次尝试所有面额，不断更新当前金额的最优结果。
Python 代码：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(len(dp)):
for coin in coins:
if i - coin < 0:
continue
dp[i] = min(dp[i], 1 + dp[i - coin])
return -1 if dp[amount] == amount + 1 else dp[amount]这里的外层循环从小到大枚举金额 i，内层循环遍历每一种硬币。
由于硬币面额都大于 0，所以 i - coin 一定小于 i。
也就是说，在计算 dp[i] 时，所依赖的 dp[i - coin] 已经在之前的循环中计算过了。
这就是自底向上迭代能够成立的原因。
最后，如果 dp[amount] 仍然等于 amount + 1，就说明目标金额无法凑出，返回 -1；否则返回实际计算出的最少硬币数量。
2.6 复杂度分析
假设目标金额为 amount，硬币面额的种类数为 m。
使用备忘录时，每个非负金额状态最多需要完整计算一次，而每次计算都需要尝试 m 种硬币。
因此，记忆化搜索的时间复杂度为：
迭代版本同样需要依次计算每个金额，并尝试所有硬币，时间复杂度也是：
空间方面，两种写法都需要保存长度为 amount + 1 的状态数组，因此空间复杂度为 。
不过，递归版本还需要使用函数调用栈，而迭代版本没有这部分额外开销。
3. 总结
这两道题虽然要求不同，但解题过程中使用了相似的动态规划思路。
斐波那契数从朴素递归入手，通过备忘录避免重复计算，再利用每个状态只依赖前两项的特点，将空间复杂度优化到 。
零钱兑换则需要在每个状态下尝试多种硬币，选择能够得到最少硬币数的方案。它同样可以使用备忘录进行记忆化搜索，也可以按照金额从小到大的顺序，逐步填充 DP 数组。
通过这两道题，我觉得写动态规划时，可以先考虑三个问题：
- 状态是什么？ 例如
fib(n)表示第n个斐波那契数，dp[i]表示凑出金额i的最少硬币数量。 - 状态之间有什么关系？ 当前状态能否由规模更小、已经解决的子问题计算出来？
- 初始状态是什么？ 哪些情况可以直接得到答案，作为递归终止条件或 DP 数组的初始化依据？
想清楚这些问题后，再考虑是使用自顶向下的备忘录，还是自底向上的迭代实现。
如果状态只依赖少量前面的结果，还可以进一步思考是否有必要保存整个 DP 数组。
聊两句
评论审核后显示有疑问、补充，或者想交流一下，都可以写在这里。
评论区将在滚动到这里时加载。