前端随笔 FE-Essay

# 动态规划解题套路框架

首先，动态规划问题的一般形式就是求最值。 动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如让你求最长递增子序列、最小编辑距离等等。

既然是要求最值，核心问题是什么？求解动态规划的核心问题时穷举。 因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值。

动态规划这么简单，就是穷举就完事了？我看到的动态规划问题都很难啊！

首先，动态规划的穷举有点特别，因为这类问题 存在「重叠子问题」 ，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会 具备「最优子结构」 ，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出 正确的「状态转移方程」 才能正确地穷举。

以上提到的 重叠子问题 、 最优子结构 、 状态转移方程 就是动态规划三要素。具体什么意思等等会举例详解，但是在实际的算法问题中， 写出状态转移方程是最困难的 ，这也是为什么很多朋友觉得动态规划问题困难的原因。

做动态规划题目的一个思维框架是：

  1. 明确 base case
  2. 明确「状态」
  3. 明确「选择」
  4. 定义 dp 数组 / 函数的含义

按上面的套路走，最后的结果就可以套这个框架：

/*
1. 初始化 base case
dp[0][0][...] = base
2. 进行状态转移
for 状态1 in 状态1的所有值
	for 状态2 in 状态2的所有值
		for ...
			dp[状态1][状态2][...] = 求最值(选择1，选择2，...)

下面通过斐波那契数列问题和凑零钱问题来详解动态规划的基本原理。前者主要是让你明白什么是重叠子问题（斐波那契数列没有求最值，所以严格来说不是动态规划），后者主要介绍如何列出状态转移方程。

# 斐波那契数列

请读者不要嫌弃这个例子简单， 只有简单的例子才能让你把精力充分集中在算法背后的通用思想和技巧上，而不会被那些隐晦的细节问题搞得莫名其妙。

# 暴力递归

斐波那契数列的数学形式就是递归，以代码呈现就是这样：

function fib(n: number): number {
  if(n === 1 || n === 2) return 1
  return fib(n - 1) + fib(n - 2)
}

学校在介绍递归的时候通常都会使用这个作为例子，我们也都知道这样写虽然代码非常简洁易懂，但是十分低效，我们画出递归树：

img

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个字问题需要的时间。

上面递归的解法中我们得知这个算法的时间复杂度是 O(2^n) ，是指数级别，原因在于大量的重复计算，因此这个算法极其低效。

这就是动态规划问题的第一个性质： 重叠子问题 。下面我们想办法解决这个问题。

# 带备忘录的递归解法

明确了问题，其实就已经把问题解决了一半。既然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案先别急着返回，先记到「备忘录中」再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题，直接把答案拿出来用，无需再去重复计算。

一般使用一个数组或者哈希表来充当这个「备忘录」：

function fib(n: number): number {
  const hashMap = new Map<number, number>()
  
  function _fib(n: number): number {
    if(n === 1 || n === 2) return 1
    if(hashMap.has(n)) return hashMap.get(n)
    const res = _fib(n - 1) + _fib(n - 2)
    hashMap.set(n, res)
    return res
  }
  
  return _fib(n)
}

现在在画出递归树，你就知道「备忘录」到底做了什么。

img

实际上，带「备忘录」的递归算法，就是把一棵存在巨量冗余的递归树通过「剪枝」，改造成一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

img

通过「剪枝」，该算法的时间复杂度从 O(2^n) 变成了 O(n) ，从指数级降低到线性级，效率得到了极大地提高。

至此，带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

啥叫「自顶向下」？注意我们刚才画的递归树，是从上而下延伸，都是从一个规模较大的原问题向下逐渐分解，直到 base case，然后逐层返回答案，这就是「自顶向下」。

啥叫「自底向上」？反过来，我们直接从最底下、最简单、问题规模最小的子问题开始往上推，直到我们想要的答案，这就是动态规划的思路，这也是为什么动态规划一般都脱离递归，而是由循环迭代完成。

# dp 数组的迭代解法

有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table，在这张表上完成「自底向上」的推算。

function fib(n: number): number {
  // base case
  const dp = [0, 1, 1]
  for(let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
}

img

画张图就非常好理解，这个 DP table 和上面「剪枝」过后的图非常想，只是反过来计算。

这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：

img

为啥叫「状态转移方程」？就是字面意思，你把 f(n) 理解成当前传入值 n 的状态，这个状态由 f(n - 1) 和 f(n - 2) 两个状态相加转移而来，所以叫「状态转移方程」。

千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。 只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。

这个例子的最后，将一个细节优化。大家可以发现，根据斐波那契数列的状态方程，当前状态只和上两个状态相关，其实不需要一个完整的 DP table 来存储所有状态，只要想办法存储之前两个状态即可。所以，可以进一步优化空间，将空间复杂度降低为 O(n) 。

function fib(n: number): number {
  if(n === 1 || n === 2) return 1
  let prev = 1
  let curr = 1
  for(let i = 3; i <= n; i++) {
    let sum = prev + curr
    prev = curr
    curr = sum
  }
  return curr
}

这个技巧就是所谓的 「状态压缩」 ，如果我们发现状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据。

有人会问，动态规划的另一个重要特性「最优子结构」怎么没有涉及？严格来说斐波那契数列并非动态规划问题，因为没有涉及求最值，以上旨在说明重叠子问题的消除方法，岩石得到最有解法逐步求精的过程。

# 凑零钱问题

这个问题会涉及到「最优子结构」，先看题目：给你 k 种面值的硬币，面值分别为 c1、c2、...、ck，每种硬币的数量无限，再给一个总金额 amount，问你 最少 需要几枚硬币凑出这个金额，如果不能凑出，算法返回 -1，算法的函数签名如下：

// coins 中是可选硬币面值，amount 是目标金额
declare function coinChange(coins: number[], amount: number): number

比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11，那么至少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1.

你认为计算机应该如何解决这个问题？显然，就是把所有可能的凑硬币方法都穷举出来，然后找找看最少需要多少枚硬币。

# 暴力递归

首先这个问题是动态规划问题，因为它具有「最优子结构」。 要复合「最有子结构」，子问题件必须互相独立。 啥叫互相独立？举个例子就是考试的时候，你每科成绩之间互相独立。

回到凑零钱问题，为什么说它符合最优子结构呢？比如原题例子中求 amount = 11，那么相当于 amount = 10 + 1 就是答案。因为硬币数量没有限制，所以子问题之间没有互相约束，而是相互独立。

既然知道这是一个动态规划问题，就要思考 如何列出正确的状态转移方程。

  1. 确定 base case ，这个很简单，显然目标金额 amount = 0 时算法返回 0，因为不需要任何硬币就可以凑出目标金额。

  2. 确定「状态」，也就是原问题和子问题中会变化的变量。 由于硬币的数量无限，硬币的面额也是题目给定的，只有目标金额会不断向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

  3. 确定「选择」，也就是导致「状态」产生变化的行为。 目标金额为什么变化呢，因为你在选择硬币，你没选择一枚硬币，就相当于减少了目标金额，所以说所有硬币的面值就是你的「选择」。

  4. 明确 dp 函数 / 数组的定义。 我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，即上面说到的「状态」；函数的返回值就是我们要求的值。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量，所以我们可以这样定义 dp 函数：

    dp(n) ：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

搞清楚以上几点，解题的框架代码就可以写出来了：

function coinChange(coins: number[], amount: number): number {
  // 定义：要凑出金额 n，至少要 dp(n) 个硬币
  function dp(n: number): number {
    let res: number
    // 做选择，选择需要硬币最少的那个结果
    for(const coin of coins) {
      res = Math.min(res, 1 + dp(n - coin))
    }
    return res
  }
  
  // 题目要求的最终结果是 dp(amount)
  return dp(amount)
}

根据伪代码，我们加上 base case 即可得到最终答案：显然目标金额为 0 时，所需硬币数量为 0；当目标金额小于 0 时，无解，返回 -1:

function coinChange(coins: number[], amount: number): number {
  function dp(n: number): number {
    // base case
    if(n === 0) return 0
    if(n < 0) return -1
    // 求最小值，所以初始化为正无穷
    let res = Infinity
    for(const coin of coins) {
			const subProblem = dp(n - coin)
      // 子问题无解，跳过
      if(subProblem === -1) continue
      res = Math.min(res, 1 + subProblem)
    }
    return res === Infinity ? -1 : res
  }
  return dp(amount)
}

至此，状态转移方程其实已经完成，以上算法已经是暴力解法，状态转移方程为：

img

所以，这个问题从答案上来说已经解决了，但是需要消除一下重叠子问题，比如说 amount = 11，coins = {1，2，5} 时画出递归树：

img

# 带备忘录的递归

类似之前的斐波那契数列问题，只需稍加修改即可通过备忘录消除重复子问题：

function coinChange(coins: number[], amount: number): number {
  // 备忘录
  const hashMap = new Map<number, number>()
  function dp(n: number): number {
    // 查看备忘录，避免重复计算
		if(hashMap.has(n)) return hashMap.get(n)
    if(n === 0) return 0
    if(n < 0) return -1
    let res = Infinity
    for(const coin of coins) {
			const subProblem = dp(n - coin)
      if(subProblem === -1) continue
      res = Math.min(res, 1 + subProblem)
    }
    // 记入备忘录
    hashMap.set(n, res === Infinity ? -1 : res)
    return hashMap.get(n)
  }
  return dp(amount)
}

显然，通过空间换时间的方式，完全消除了子问题的冗余，让空间复杂度降低为线性级 O(n) 。

# dp 数组的迭代解法

当然我们也可以使用自底向上的思路来解决问题，关于「状态」「选择」和 base case 与之前没有差别，dp 数组的定义和 dp 函数类似，也是把「状态」，也就是目标金额作为常量。不过 dp 函数体现在函数参数，dp 数组体现在数组索引：

dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。

function coinChange(coins: number[], amount: number): number {
	// 数组大小为 amount + 1，初始值也为 amount + 1
  const dp = Array(amount + 1).fill(amount + 1)
  // base case
  dp[0] = 0
  // 外层遍历所有状态的所有值
  for(let i = 0; i < dp.length; i++) {
    // 内层求所有选择的最小值
    for(const coin of coins) {
      // 子问题无解，跳过
      if(i - coin < 0) continue
      dp[i] = Math.min(dp[i], 1 + dp[i - coin])
    }
  }
  return dp[amount] === amount + 1 ? -1 : dp[amount]
}

img

PS：为啥 dp 数组初始化为 amount + 1 呢，因为凑成 amount 金额的硬币数最多只可能等于 amount（全用 1 元面值的硬币），所以初始化为 amount + 1 就相当于初始化为正无穷，以便于后续取最小值。

← 状态压缩：对动态规划进行降维打击.md →