动态规划

动态规划

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划用来解决一定条件下的最优解，比如：

• 自动寻路哪种走法最优？
• 背包装哪些物品空间利用率最大？
• 怎么用最少的硬币凑零钱？

动态规划与暴力、回溯算法的区别

所有动态规划问题都能通过暴力方法解决！所有最优解问题都可以通过暴力方法尝试（以及回溯算法），最终找出最优的那个。 暴力算法几乎可以解决一切问题。回溯算法的特点是，通过暴力尝试不同分支，最终选择结果最优的线路。

而动态规划也有分支概念，但不用把每条分支尝试到终点，而是在走到分叉路口时，可以直接根据前面各分支的表现，直接推导出下一步的最优解！然而无论是直接推导，还是前面各分支判断，都是有条件的。动态规划可解问题需同时满足以下三个特点：

1. 存在最优子结构。
2. 存在重复子问题。
3. 无后效性。

存在最优子结构

即子问题的最优解可以推导出全局最优解。

什么是子问题？比如寻路算法中，走完前几步就是相对于走完全程的子问题，必须保证走完全程的最短路径可以通过走完前几步推导出来，才可以用动态规划。

不要小看这第一条，动态规划就难在这里，你到底如何将最优子结构与全局最优解建立上关系？

• 对于爬楼梯问题，由于每层台阶都是由前面台阶爬上来的，因此必然存在一个线性关系推导。
• 如果变成二维平面寻路呢？那么就升级为二维问题，存在两个变量 i,j 与上一步之间关系了。
• 如果是背包问题，同时存在物品数量 i、物品重量 j 和物品质量 k 三个变量呢？那就升级为三位问题，需要寻找三个之间的关系。

依此类推，复杂度可以上升到 N 维，维度越高思考的复杂度就越高，空间复杂度就越需要优化。

存在重复子问题

即同一个子问题在不同场景下存在重复计算。

比如寻路算法中，同样两条路线的计算中，有一段路线是公共的，是计算的必经之路，那么只算一次就好了，当计算下一条路时，遇到这个子路，直接拿第一次计算的缓存即可。典型例子是斐波那契数列，对于 f(3) 与 f(4)，都要计算 f(1) 与 f(2)，因为 f(3) = f(2) + f(1)，而 f(4) = f(3) + f(2) = f(2) + f(1) + f(2)。

这个是动态规划与暴力解法的关键区别，动态规划之所以性能高，是因为 不会对重复子问题进行重复计算，算法上一般通过缓存计算结果或者自底向上迭代的方式解决（记忆化递归），但核心是这个场景要存在重复子问题。

当你觉得暴力解法可能很傻，存在大量重复计算时，就要想想是哪里存在重复子问题，是否可以用动态规划解决了。

无后效性

即前面的选择不会影响后面的游戏规则。

一旦一个子问题的求解得到结果，以后的计算过程就不会修改它，这样的特点叫做无后效性，求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次，具有天然剪枝的功能，从而减少计算量。

寻路算法中，不会因为前面走了 B 路线而对后面路线产生影响。斐波那契数列因为第 N 项与前面的项是确定关联，没有选择一说，所以也不存在后效性问题。

解法套路 - 状态转移方程

解决动态规划问题的核心就是写出状态转移方程，所谓状态转移，即通过某些之前步骤推导出未来步骤。

状态转移方程一般写为 dp(i) = 一系列 dp(j) 的计算，其中 j < i。

其中 i 与 dp(i) 的含义很重要，一般 dp(i) 直接代表题目的答案，i 就有技巧了。比如斐波那契数列，dp(i) 表示的答案就是最终结果，i 表示下标，由于斐波那契数列直接把状态转移方程告诉你了 f(x) = f(x-1) + f(x-2)，那么根本连推导都不必了。

对于复杂问题，难在如何定义 i 的含义，以及下一步状态如何通过之前状态推导。

爬楼梯问题

爬楼梯是一道简单题，题目如下：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？（给定 n 是一个正整数）

首先 dp(i) 就是问题的答案（解法套路，dp(i) 大部分情况就是答案，这样解题思路会最简化），即爬到第 i 阶台阶的方法数量，那么 i 自然就是要爬到第几阶台阶。

我们首先看是否存在 最优子结构？因为只能往上爬，所以第 i 阶台阶有几种爬方完全取决于前面有几种爬方，而一次只能爬 1 或 2 个台阶，所以第 i 阶台阶只可能从第 i-1 或 i-2 个台阶爬上来的，所以第 i 个台阶的爬法就是 i-1 与 i-2 总爬法之和。所以显然有最优子结构，连状态转移方程都呼之欲出了。

再看是否存在 存在重复子问题，其实爬楼梯和斐波那契数列类似，最终的状态转移方程是一样的，所以显然存在重复子问题。当然直观来看也容易分析出，10 阶台阶的爬法包含了 8、9 阶的爬法，而 9 阶台阶爬法包含了 8 阶的，所以存在重复子问题。

最后看是否 无后效性？由于前面选择一次爬 1 个或 2 个台阶并不会影响总台阶数，也不会影响你下一次能爬的台阶数，所以无后效性。如果你爬了 2 个台阶，因为太累，下次只能爬 1 个台阶，就属于有后效性了。或者只要你一共爬了 3 次 2 阶，就会因为太累而放弃爬楼梯，直接下楼休息，那么问题提前结束，也属于有后效性。

所以爬楼梯的状态转移方程为：

• dp(i) = dp(i-1) + dp(i-2)
• dp(1) = 1
• dp(2) = 2

注意，因为 1、2 阶台阶无法应用通用状态转移方程，所以要特殊枚举。这种枚举思路在代码里其实就是 递归终结条件，也就是作为函数 dp(i) 不能无限递归，当 i 取值为 1 或 2 时直接返回枚举结果（对这道题而言）。所以在写递归时，一定要优先写上递归终结条件。

然后我们考虑，对于第一阶台阶，只有一种爬法，这个没有争议吧。对于第二阶台阶，可以直接两步跨上来，也可以走两个一步，所以有两种爬法，也很容易理解，到这里此题得解。

function dp(i: number) {
  switch (i) {
    case 1:
      return 1
    case 2:
      return 2
    default:
      return dp(i - 1) + dp(i - 2)
  }
}

return dp(n)

当然这样写重复计算了子结构，所以我们不要每次傻傻的执行 dp(i - 1)（因为这样计算了超多重复子问题），我们需要用缓存兜底：

const cache: number[] = []

function dp(i: number) {
  switch (i) {
    case 1:
      cache[i] = 1
      break
    case 2:
      cache[i] = 2
      break
    default:
      cache[i] = cache[i - 1] + cache[i - 2]
  }

  return cache[i]
}

// 既然用了缓存，最好子底向上递归，这样前面的缓存才能优先算出来
for (let i = 1; i <= n; i++) {
  dp(i)
}

return cache[n]

当然这只是简单的一维线性缓存，更高级的缓存模式还有 滚动缓存。我们观察发现，这道题缓存空间开销是 O(n)，但每次缓存只用了上两次的值，所以计算到 dp(4) 时，cache[1] 就可以扔掉了，或者说，我们可以滚动利用缓存，让 cache[3] 占用 cache[1] 的空间，那么整体空间复杂度可以降低到 O(1)，具体做法是：

const cache: [number, number] = []

function dp(i: number) {
  switch (i) {
    case 1:
      cache[1] = 1
      break
    case 2:
      cache[0] = 2
      break
    default:
      cache[i % 2] = cache[(i - 1) % 2] + cache[(i - 2) % 2]
  }

  return cache[i % 2]
}

for (let i = 1; i <= n; i++) {
  dp(i)
}

return cache[n % 2]

通过取余，巧妙的让缓存永远交替占用 cache[0] 与 cache[1]，达到空间利用最大化。当然，这道题因为状态转移方程是连续用了前两个，所以可以这么优化，如果遇到用到之前所有缓存的状态转移方程，就无法使用滚动缓存方案了。然而还有更高级的多维缓存，这个后面提到的时候再说。

力扣

最大子序和

最长递增子序列

最长递增子序列是一道中等题，题目如下：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

其实之前的 精读《DOM diff 最长上升子序列》 有详细解析过这道题，包括还有更优的贪心解法，不过我们这次还是聚焦在动态规划方法上。

这道题与上一道的区别就是，首先递增，其次不连续。

按照套路，dp(i) 就表示以第 i 个字符串结尾的最长上升子序列长度，那么重点是，dp(i) 怎么通过之前的推导出来呢？

由于是不连续的，因此不能只看 dp(i-1) 了，因为 nums[i] 项与 dp(j)（其中 0 <= j < i）组合后都可能达到最大长度，因此需要遍历所有 j，尝试其中最大长度的组合。

所以状态转移方程为：

dp[i] = max(dp[j]) + 1，其中 0<=j<i 且 num[j]<num[i]。

这道题的出现，预示着较为复杂的状态转移方程的出现，即第 i 项不是简单由 i-1 推导，而是由之前所有 dp(j) 推导，其中 0<=j<i。

除此之外，还有推导变种，即根据 dp(dp(i)) 推导，即函数里套函数，这类问题由于加深了一层思考脑回路，所以相对更难。我们看一道这样的题目：最长有效括号。