精读《算法 - 动态规划》

不少人以为动态规划很难，甚至认为面试出动态规划题目是在为难候选人，这可能产生一个错误潜意识：认为动态规划不须要掌握。前端

其实动态规划很是有必要掌握：git

1. 很是锻炼思惟。动态规划是很是锻炼脑力的题目，虽然有套路，但每道题解法思路差别很大，做为思惟练习很是合适。
2. 很是实用。动态规划听起来很高级，但实际上思路和解决的问题都很常见。

动态规划用来解决必定条件下的最优解，好比：github

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

其实这些问题乍一看都挺难的，毕竟都不是一眼能看出答案的问题。但获得最优解又很是重要，谁能忍受游戏中寻路算法绕路呢？谁不但愿背包放的东西更多呢？因此咱们必定要学好动态规划。面试

精读

动态规划不是魔法，它也是经过暴力方法尝试答案，只是方式更加 “聪明”，使得实际上时间复杂度并不高。算法

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

上面这句话也说明了，全部动态规划问题都能经过暴力方法解决！是的，全部最优解问题均可以经过暴力方法尝试（以及回溯算法），最终找出最优的那个。typescript

暴力算法几乎能够解决一切问题。回溯算法的特色是，经过暴力尝试不一样分支，最终选择结果最优的线路。数组

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

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 阶台阶的爬法包含了 八、9 阶的爬法，而 9 阶台阶爬法包含了 8 阶的，因此存在重复子问题。

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

因此爬楼梯的状态转移方程为：

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

注意，由于 一、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[i % 2] = 1;
      break;
    case 2:
      cache[i % 2] = 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 ，找到一个具备最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

首先按照爬楼梯的套路，dp(i) 就表示最大和，因为整数数组可能存在负数，因此越多数相加，和不必定越大。

接着看 i，对于数组问题，大部分 i 均可以表明以第 i 位结尾的字符串，那么 dp(i) 就表示以第 i 位结尾的字符串的最大和。

可能你以为以 i 结尾，就只能是 [0-i] 范围的值，那么 [j-i] 范围的字符串不就被忽略了？其实否则，[j-i] 若是是最大和，也会被包含在 dp(i) 里，由于咱们状态转移方程能够选择不连上 dp(i-1)。

如今开始解题：首先题目是最大和的连续子数组，通常连续的都比较简单，由于对于 dp(i)，要么和前面连上，要么和前面断掉，因此状态转移方程为：

• dp(i) = dp(i-1) + nums[i] 若是 dp(i-1) > 0。
• dp(i) = nums[i] 若是 dp(i-1) <= 0。

怎么理解呢？就是第 i 个状态能够直接由第 i-1 个状态推导出来，既然 dp(i) 是指以第 i 个字符串结尾的最大和，那么 dp(i-1) 就是以第 i-1 个字符串结尾的最大和，并且此时 dp(i-1) 已经算出来了，那么 dp(i) 怎么推导就清楚了：

由于字符串是连续的，因此 dp(i) 要么是 dp(i-1) + nums[i]，要么就直接是 nums[i]，因此选择哪一种，取决于前面的 dp(i-1) 是不是正数，由于以 i 结尾必定包含 nums[i]，因此 nums[i] 无论是正仍是负，都必定要带上。 因此容易得知，dp(i-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)) 推导，即函数里套函数，这类问题因为加深了一层思考脑回路，因此相对更难。咱们看一道这样的题目：最长有效括号。

最长有效括号

最长有效括号是道困难题，题目以下：

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

这道题之因此是困难题，就由于状态转移方程存在嵌套思惟。

咱们首先按套路定义 dp(i) 为答案，即以第 i 下标结尾的字符串中最长有效括号长度。看出来了吗？通常字符串题目中，i 都是以字符串下标结尾来定义，不多有定义为开头或者别的定义行为。固然非字符串问题就不是这样了，这个在后面再说。

咱们继续题目，若是 s[i] 是 (，那么不可能组成有效括号，由于最右边必定不闭合，因此考虑 s[i] 为 ) 的场景。

若是 s[i-1] 为 (，那么构成了 ...() 之势，最后两个自成合法闭合，因此只要看前面的便可，即 dp(i-2)，因此这种场景的状态转移方程为：

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

若是 s[i-1] 是 ) 呢？构成了 ...)) 的状态，那么只有 i-1 是合法闭合的，且这个合法闭合段以前必须是 ( 与第 i 项造成闭合，才构成此时最长有效括号长度，因此这种场景的状态转移方程为：

dp(i) = dp(i-1) + dp(i - dp(i-1) - 2) + 2，你能够结合下面的图来理解：

<img width=300 src="https://img.alicdn.com/imgextra/i1/O1CN016tRvXm1o4p8U1Plfk_!!6000000005172-2-tps-1088-378.png">

能够看到，dp(i-1) 就是第二条横线的长度，而后若是红色括号匹配的话，长度又 +2，最后别忘了最左边若是有知足匹配的也要带上，这就是 dp(i - dp(i-1) - 2)，因此加到一块儿就是这种场景的括号最大长度。

到这里，一维动态规划问题深度基本上探索完了，在进入多维动态规划问题前，还有一类一维动态规划问题，属于表达式不难，也没有这题这么复杂的嵌套 DP，可是思惟复杂度极高，你必定不要盯着全流程看，那样复杂度过高，你须要充分承认 dp(i-x) 已经算出来部分的含义，进行高度抽象的思考。

栅栏涂色

栅栏涂色是一道困难题，题目以下：

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每一个栅栏柱能够用其中一种颜色进行上色。

你须要给全部栅栏柱上色，而且保证其中相邻的栅栏柱 最多连续两个 颜色相同。而后，返回全部有效涂色的方案数。

这道题 k 和 n 都很是巨大，常规暴力解法甚至普通 DP 都会超时。选择 i 的含义也很重要，这里 i 到底表明用几种颜色仍是几个栅栏呢？选择栅栏会好作一些，由于栅栏是上色的主体。这样 dp(i) 就表示上色前 i 个栅栏的全部涂色方案。

首先看下递归终止条件。因为最多连续两个颜色相同，所以 dp(0) 与 dp(1) 分别是 k 与 k*k，由于每一个栅栏随便刷颜色，自由组合。那么 dp(2) 有三个栅栏，非法状况是三个栅栏全同色，因此用全部可能减掉非法便可，非法场景只有 k 中，因此结果是 k*k*k - k。

那么考虑通常状况，对于 dp(i) 有几种涂色方案呢？直接思考状况太多，咱们把状况一分为二，考虑 i 与 i-1 颜色相同与不一样两种状况考虑。

若是 i 与 i-1 颜色相同，那么为了合法，i-1 确定不能与 i-2 颜色相同了，不然就三个同色，这样的话，无论 i-2 是什么颜色，i-1 与 i 都只能少取一种颜色，少取的颜色就是 i-2 的颜色，所以 [i-1,i] 这个区间有 k-1 中取色方案，前面有 dp(i-2) 种取色方案，相乘就是最终方案数：dp(i-2) * (k-1)。

这背后其实存在动态思惟，即每种场景的 k-1 都是不一样的颜色组合，只是不管前面 dp(i-2) 是何种组合，后面两个栅栏必定有 k-1 种取法，虽然颜色组合的色值不一样，但颜色组合数量是不变的，因此能够统一计算。理解这一点很是关键。

若是 i 与 i-1 颜色不一样，那么第 i 项只有 k-1 种取法，同样也是动态的，由于永远不能和 i-1 颜色相同。最后乘上 dp(i-1) 的取色方案，就是总方案数：dp(i-1) * (k-1)。

因此最后总方案数就是二者之和，即 dp(i) = dp(i-2) * (k-1) + dp(i-1) * (k-1)。

这道题的不一样之处在于，变化太多，任何一个栅栏取的颜色都会影响后面栅栏要取的颜色，乍一看以为是个有后效性的题目，没法用动态规划解决。但实际上，虽然有后效性，但若是进行合理的拆解，后面栅栏的总可能性 k-1 是不变的，因此考虑总可能性数量，是无后效性的，所以站在方案总数上进行抽象思考，才可能破解此题。

接下来介绍多维动态规划，从二维开始。二维动态规划就是用两个变量表示 DP，即 dp(i,j)，通常在二维数组场景出现较多，固然也有一些两个数组之间的关系，也属于二维动态规划，为了继续探讨字符串问题，我选择了字符串问题的二维动态规划范例，编辑距离这道题来讲明。

编辑距离

编辑距离是一道困难题，题目以下：

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操做数。

你能够对一个单词进行以下三种操做：

• 插入一个字符
• 删除一个字符
• 替换一个字符

只要是字符串问题，基本上 i 都表示以第 i 项结尾的字符串，但这道题有两个单词字符串，为了考虑任意匹配场景，必须用两个变量表示，即 i j 分别表示 word1 与 word2 结尾下标时，最少操做次数。

那么对于 dp(i,j) 考虑 word1[i] 与 word2[j] 是否相同，最后经过双重递归，先递归 i，在递归内再递归 j，答案就出来了。

假设最后一个字符相同，即 word1[i] === word2[j] 时，因为最后一个字符不用改就相同了，因此操做次数就等价于考虑到前一个字符，即 dp(i,j) = dp(i-1,j-1)

假设最后一个字符不一样，那么 最后一步 有三种模式能够获得：

1. 假设是替换，即 dp(i,j) = dp(i-1,j-1) + 1，由于替换最后一个字符只要一步，而且和前面字符没什么关系，因此前面的最小操做次数直接加过来。
2. 假设是插入，即 word1 插入一个字符变成 word2，那么只要变换到这一步再 +1 插入操做就好了，变换到这一步因为插入一个就好了，所以 word1 比 word2 少一个单词，其它都同样，要变换到这一步，就要进行 dp(i,j-1) 的变换，所以 dp(i,j) = dp(i,j-1) + 1。。
3. 假设是删除，即 word1 删除一个字符变成 word2，同理，要进行 dp(i-1,j) 的变化后多一步删除，所以 dp(i,j) = dp(i-1,j) + 1。

因为题目取操做最少次数，因此这三种状况取最小便可，即 dp(i,j) = min(dp(i-1,j-1), dp(i,j-1), dp(i-1,j)) + 1。

因此同时考虑了最后一个字符是否相同后，合并了的状态转移方程就是最终答案。

咱们再考虑终止条件，即 i 或 j 为 -1 时的状况，由于状态转移方程 i 和 j 不断减少，确定会减小到 0 或 -1，由于 0 是字符串还有一个字符，相对好比考虑 -1 字符串为空时方便，所以咱们考虑 -1 时做为边界条件。

当 i 为 -1 时，即 word1 为空，此时要变换为 word2 很显然，只有插入 j 次是最小操做次数，所以此时 dp(i,j) = j；同理，当 j 为 -1 时，即 word2 为空，此时要删除 i 次，所以操做次数为 i，因此 dp(i,j) = i。

非字符串问题

说到这，相信你在字符串动规问题上已经如鱼得水了，咱们再看看非字符串场景的动规问题。非字符串场景的动规比较经典的有三个，第一是矩形路径最小距离，或者最大收益；第二是背包问题以及变种；第三是打家劫舍问题。

这些问题解决方式都同样，只是对于 dp(i) 的定义略有区别，好比对于矩形问题来讲，dp(i,j) 表示走到 i,j 格子时的最小路径；对于背包问题，dp(i,j) 表示装了第 i 个物品时，背包还剩 j 空间时最大价格；对于打家劫舍问题，dp(i) 表示打劫到第 i 个房间时最大收益。

由于篇幅问题这里就不一详细介绍了，只简单说明一下矩形问题于打家劫舍问题。

对于矩形问题，状态转移方程重点看上个状态是如何转移过来的，通常矩形只能向右或者向下移动，路途可能有一些障碍物不能走，咱们要作分支判断，而后选择一条符合题目最值要求的路线做为当前 dp(i) 的转移方程便可。

对于打家劫舍问题，因为不能同时打劫相邻的房屋，因此对于 dp(i)，要么为了打劫 i-1 而不打劫第 i 间，或者打劫 i-2 于第 i 间，取这两种终态的收益最大值便可，即 dp(i) = max(dp(i-1), dp(i-2) + coins[i])。

总结

动态规划的核心分为三步，首先定义清楚状态，即 dp(i) 是什么；而后定义状态转移方程，这一步须要一些思考技巧；最后思考验证一下正确性，即尝试证实你写的状态转移方程是正确的，在这个过程要作到状态转移的不重不漏，全部状况都被涵盖了进来。

动态规划最经典的仍是背包问题，因为篇幅缘由，可能下次单独出一篇文章介绍。

讨论地址是： 精读《算法 - 动态规划》· Issue #327 · dt-fe/weekly

若是你想参与讨论，请 点击这里，每周都有新的主题，周末或周一发布。前端精读 - 帮你筛选靠谱的内容。

关注 前端精读微信公众号

<img width=200 src="https://img.alicdn.com/tfs/TB165W0MCzqK1RjSZFLXXcn2XXa-258-258.jpg">

版权声明：自由转载-非商用-非衍生-保持署名（ 创意共享 3.0 许可证）