「数据结构与算法」动静布局学习笔记：线性动静布局

用动静布局解决问题的过程有以下几个关键点：

• <font color=”#dd0000″>状态定义</font>
• <font color=”#dd0000″>状态的转移</font>
• 初始化
• 边界条件

<font color=”#dd0000″>状态定义 </font>
就是 定义子问题 ，如何示意指标规模的问题和更小规模的问题。例如常见的办法：定义状态 dp[n]，示意规模为 n 的问题的解，dp[n – 1] 就示意规模为 n – 1 的子问题的解。<font color=”#dd0000″> 在实战中 dp[n] 的具体含意须要首先整顿分明再往下做</font>。

<font color=”#dd0000″>状态转移 </font>
就是 子问题之间的关系 ，例如定义好状态 dp[n]，此时子问题是 dp[n-1] 等，并且大规模的问题的解依赖小规模问题的解，此时须要晓得 怎么通过小规模问题的解推出大规模问题的解。这一步就是列状态转移方程的过程。个别的状态转移方程能够写成如下模式

dp[n] = f(dp[i]) 其中 i < n

依照 状态定义 和状态转移 的常见模式，能够对动静布局进行分类。

其中 线性动静布局 的次要特点是 状态的推导 是依照问题规模 i 从小到大顺次推过去的，较大规模的问题的解依赖较小规模的问题的解。

这里问题规模为 i 的含意是思考前 i 个元素 [0..i] 时问题的解。

线性动静布局简介

线性动静布局的次要特点是 状态的推导是依照问题规模 i 从小到大顺次推过去的，较大规模的问题的解依赖较小规模的问题的解。

这里问题规模为 i 的含意是思考前 i 个元素 [0..i] 时问题的解。

状态定义：

dp[n] := [0..n] 上问题的解

状态转移：

dp[n] = f(dp[n-1], ..., dp[0])

从以上状态定义和状态转移能够看出，大规模问题的状态只与较小规模的问题无关 ，而问题规模齐全用一个变量 i 示意，i 的大小示意了问题规模的大小，因而 从小到大推 i 直至推到 n，就失去了大规模问题的解，这就是线性动静布局的过程。

线性动静布局是动静布局中最根本的一类。问题的模式、dp 状态和方程的设计、以及与其它算法的联合下面变动很多。依照 dp 方程中各个维度的含意，能够大抵总结出几个支流的问题类型：

• 单串
• 双串
• 矩阵
• 无串

单串

单串 dp[i] 线性动静布局最简略的一类问题，输出是一个串。

线性动静布局中单串 dp[i] 的问题，状态的推导方向以及推导公式如下：

依赖比 i 小的 O(1) 个子问题：dp[n] 只与常数个小规模子问题无关

状态的推导过程：

dp[i] = f(dp[i - 1], dp[i - 2], ...)

工夫复杂度 O(n)，空间复杂度 O(n) 能够优化为 O(1)，例如 LeetCode 70, 801, 790, 746 都属于这类。
如上图所示，尽管蓝紫色局部的 dp[i-1], dp[i-2], …, dp[0] 均曾经计算过，但计算橙色的以后状态时，仅用到 dp[i-1]，这属于 比 i 小的 O(1) 个子问题 。
例如，当 f(dp[i-1], …) = dp[i-1] + nums[i] 时，以后状态 dp[i] 仅与 dp[i-1] 无关。这个例子是一种数据结构前缀和的状态计算形式。

例题：

一个数组有很多个子数组，求哪个子数组的和最大。能够 依照子数组的最初一个元素来分子问题，确定子问题后设计状态

dp[i] := [0..i] 中，以 nums[i] 结尾的最大子数组和

状态的推导是依照 i 从 0 到 n – 1 按程序推的，推到 dp[i]，时，dp[i – 1], …, dp[0] 曾经计算完。因为 子数组是间断的 ，所以 子问题 dp[i] 其实只与子问题 dp[i – 1] 无关 。如果 [0..i-1] 上以 nums[i-1] 结尾的最大子数组和(缓存在 dp[i-1] ) 为非正数，则以 nums[i] 结尾的最大子数组和，就在 dp[i-1] 的根底上加上 nums[i] 就是 dp[i] 的后果否则以 i 结尾的子数组就不要 i-1 及之前的数，因为选了的话子数组的和只会更小。
因而，状态转移方程如下：

dp[i] = nums[i] + max(dp[i - 1], 0)

依赖比 i 小的 O(n) 个子问题：dp[n] 与此前的更小规模的所有子问题 dp[n – 1], dp[n – 2], …, dp[1] 都可能有关系

状态推导过程如下：

dp[i] = f(dp[i - 1], dp[i - 2], ..., dp[0])

如上图所示，计算橙色的以后状态 dp[i] 时，蓝紫色局部为 此前计算过的状态 dp[i-1], …, dp[0] 均有可能被用到 ，在计算 dp[i] 时须要将它们遍历一遍实现计算。
其中 f 常见的有 max/min，可能还会对 i-1,i-2,…,0 有一些筛选条件，但推导 dp[n] 时仍然是 O(n) 级的子问题数量。

双串

有两个输出从串，长度别离为 m, n，此时子问题须要用 i, j 两个变量示意，别离代表第一个串和第二个串思考的地位 dp[i][j]:= 第一串思考 [0..i]，第二串思考[0..j] 时，原问题的解

较大规模的子问题 只与 常数个较小规模的子问题 无关，其中较小规模可能是 i 更小，或者是 j 更小，也能够是 i，j 同时变小。
其中一种最常见的状态转移模式：推导 dp[i][j] 时，dp[i][j] 仅与 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]

线性动静布局中双串 dp[i][j] 的问题，状态的推导方向以及推导公式如下

如图所示，绿色局部的 dp[i-1 ~ 0][j-1 ~ 0] 均曾经计算过，但计算橙色的以后状态时，仅用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]，即比 i, j 小的 O(1)O(1) 个子问题。

这种模式的线性 DP 的代码常见写法

for i = 1..m
    for j = 1..n
        dp[i][j] = f(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])

工夫复杂度 O(mn)O(mn)，空间复杂度 O(mn)O(mn)

以上是 O(1)O(1) 转移的状况，即计算 dp[i][j] 时，尽管绿色局部的子问题均曾经计算完，但只须要用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]。也可能呈现更高复杂度的转移，相似单串中依赖比 i 小的 O(n)O(n) 个子问题的状况。

经典问题：最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

思路

单个数组或者字符串要用动静布局时，能够把动静布局 dp[i] 定义为 nums[0:i] 中想要求的后果；当两个数组或者字符串要用动静布局时，能够把动静布局定义成两维的 dp[i][j] ，其含意是在 A[0:i] 与 B[0:j] 之间匹配失去的想要的后果。

状态定义

能够定义 dp[i][j]  示意 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。（注： text1[0:i-1] 示意的是 text1 的 第 0 个元素到第 i – 1 个元素，两端都蕴含）
之所以 dp[i][j]  的定义不是 text1[0:i] 和 text2[0:j] ，是为了不便当 i = 0 或者 j = 0 的时候， dp[i][j] 示意的为空字符串和另外一个字符串的匹配，这样 dp[i][j]  能够初始化为 0。

状态转移

• 当 text1[i - 1] == text2[j - 1] 时，阐明两个子字符串的最初一位相等，所以最长公共子序列又减少了 1，所以 dp[i][j] = dp[i - 1][j - 1] + 1；举个例子，比方对于 ac 和 bc 而言，他们的最长公共子序列的长度等于 a 和 b 的最长公共子序列长度 0 + 1 = 1。
• 当 text1[i - 1] != text2[j - 1]  时，阐明两个子字符串的最初一位不相等，那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。举个例子，比方对于 ace 和 bc 而言，他们的最长公共子序列的长度等于 ① ace 和 b 的最长公共子序列长度 0 与 ② ac 和 bc 的最长公共子序列长度 1 的最大值，即 1。

综上状态转移方程为：

dp[i][j] =
1. dp[i-1][j-1] + 1  (text1[i] == text2[j])
2. max(dp[i][j-1], dp[i-1][j])  (text1[i] != text2[j])

状态初始化

初始化就是要看当 i = 0 与 j = 0 时， dp[i][j] 应该取值为多少。

当 i = 0 时， dp[0][j] 示意的是 text1text1 中取空字符串 跟 text2 的最长公共子序列，后果必定为 0。
当 j = 0 时， dp[i][0] 示意的是 text2text2 中取空字符串 跟 text1 的最长公共子序列，后果必定为 0。
综上，当 i = 0 或者 j = 0 时， dp[i][j] 初始化为 0。

经典问题：最长重复子数组

给两个整数数组 A 和 B，返回两个数组中公共的、长度最长的子数组的长度。

思路

辨别两个概念：

• 子序列能够是不间断的
• 子数组（子字符串）须要是间断的

状态定义

定义 dp[i][j] 为以 nums1[i - 1] 和 nums2[j - 1] 为开端项的公共子数组的长度。

状态转移

• 当 nums1[i - 1] == nums2[j - 1] 时，以 nums1[i - 1] 和 nums2[j - 1] 为开端项的公共子数组 dp[i][j] 的长度保底为 1，要思考它俩的前缀数组 dp[i - 1][j - 1] 能为它俩提供多大的公共长度。
• 当 nums1[i - 1] != nums2[j - 1]  时，以 nums1[i - 1] 和 nums2[j - 1] 为开端项的公共子数组 dp[i][j] 的长度为 0。

综上状态转移方程为：

dp[i][j] =
1. dp[i-1][j-1] + 1  (nums1[i] == nums2[j])
2. 0  (nums1[i] != nums2[j])

经典问题：编辑间隔

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所应用的起码操作数。
你能够对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

思路

咱们能够对任意一个单词进行三种操作：

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

题目给定了两个单词，设为 A 和 B，这样咱们就可能六种操作方法（插入 A、插入 B、删除 A、删除 B、替换 A、替换 B）。

但能够发现：

• 对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge，单词 B 为 dog 时，既能够删除单词 A 的最初一个字符 e，失去雷同的 dog，也能够在单词 B 开端增加一个字符 e，失去雷同的 doge
• 对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的
• 对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat，单词 B 为 cat 时，批改单词 A 的第一个字母 b -> c，和批改单词 B 的第一个字母 c -> b 是等价的。

这样以来，实质不同的操作实际上只有三种：

• 在单词 A 中插入一个字符
• 在单词 B 中插入一个字符
• 批改单词 A 的一个字符

状态定义

定义 dp[i][j] 为word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短须要操作的次数。
须要思考 word1 或 word2 一个字母都没有，即全减少 or 全删除的状况，所以预留 dp[0][j] 和 dp[i][0] 。

状态转移

• D[i][j-1] 为 word1 的前 i 个字符和 word2 的前 j - 1 个字符编辑间隔的子问题。即对于 word2 的第 j 个字符，咱们在 word1 的开端增加了一个雷同的字符，那么 D[i][j] 最小能够为 D[i][j-1] + 1
• D[i-1][j] 为 word1 的前 i - 1 个字符和 word2 的前 j 个字符编辑间隔的子问题。即对于 word1 的第 i 个字符，咱们在 word2 的开端增加了一个雷同的字符，那么 D[i][j] 最小能够为 D[i-1][j] + 1
• D[i-1][j-1] 为 word1 前 i - 1 个字符和 word2 的前 j - 1 个字符编辑间隔的子问题。即对于 word2 的第 j 个字符，咱们批改 word1 的第 i 个字符使它们雷同，那么 D[i][j] 最小能够为 D[i-1][j-1] + 1。特地地，如果 word1 的第 i 个字符和 word2 的第 j 个字符本来就雷同，那么咱们实际上不须要进行批改操作。在这种状况下， D[i][j] 最小能够为 D[i-1][j-1]

综上状态转移方程为：

dp[i][j] =
1. min(dp[i][j−1] + 1, dp[i−1][j] + 1, dp[i−1][j−1]) (word1[i - 1] == word2[j - 1])
2. min(dpi][j−1], dp[i−1][j], dp[i−1][j−1]) + 1 (word1[i - 1] != word2[j - 1])

总结

动静布局中最重要的三个概念：最优子结构 ， 重复子问题 ， 无后效性。

• 最优子结构 ：如果问题的最优解所蕴含的 子问题的解也是最优的，就称该问题具备最优子结构。
• 无后效性 ：即某阶段状态 一旦确定 ，就 不受这个状态当前决策的影响。也就是说，某状态当前的过程不会影响以前的状态，只与以后状态无关。
• 重复子问题 ：即 子问题之间是不独立的 ，一个子问题 在下一阶段决策中可能被屡次应用到。（该性质并不是动静布局实用的必要条件，然而如果没有这条性质，动静布局算法同其余算法相比就不具备劣势）

参考

https://leetcode-cn.com/leetb…