双序列型 | Civilization Museum

type

status

password

date

slug

summary

题型

输入序列 A[0,...,n-1]和B[0,...,m-1]

dp[i,j] 表示输入为 A[0,...,i]和B[0,...,j]时的状态，要建立 dp[i,j]与dp[i-1,j]、dp[i-1,j-1]、dp[i,j-1]、dp[i-2,j]、dp[i-2,j-1]、...的联系

二维状态矩阵的压缩一般压缩成一行

1143. 最长公共子序列 - 力扣

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

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

示例 1：输入：text1 = "abcde", text2 = "ace" 输出：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。

题解一

状态：假设字符串 text1 和 text2 的长度分别为 m 和 n，创建行列的二维数组 dp，其中 dp[i][j]表示 text1[0:i]左闭右开和 text2[0:j] 的最长公共子序列的长度。

边界条件：

当时，text1[0:i]=text1[0:0] 为空，空字符串和任何字符串的最长公共子序列的长度都是，因此对任意，有 dp[0][j]=0；
当时，text2[0:j]=text2[0:0] 为空，同理可得，对任意，有 dp[i][0]=0。

状态转移方程：

当，考虑以下两项，应取两项中的长度较大的一项，因此 dp[i][j]=max(dp[i−1][j],dp[i][j−1])。

text1[0:i-1]和 text2[0:j] 的最长公共子序列dp[i−1][j]。dp[i−1][j]一定包含dp[i-1][j-1]

text1[0:i] 和 text2[0:j−1] 的最长公共子序列dp[i][j-1]。dp[i][j-1]一定包含dp[i-1][j-1]

当时，将这两个相同的字符称为公共字符，考虑 text1[0:i−1] 和 text2[0:j−1] 的最长公共子序列，再增加一个字符（即公共字符）即可得到 text1[0:i] 和 text2[0:j] 的最长公共子序列，因此 dp[i][j]=dp[i−1][j−1]+1。

💡

且。

自顶向下

自底向上

算法

自底向上-状态压缩（注意循环的顺序有区别，取%的那一行在外层循环）

718. 最长重复子数组

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

示例：输入： A: [1,2,3,2,1] B: [3,2,1,4,7] 输出：3 解释：长度最长的公共子数组是 [3, 2, 1] 。

题解一

状态：假设数组 A 和 B 的长度分别为 m 和 n，创建行列的二维数组 dp，其中 dp[i][j]表示 A[0:i] 和 B[0:j] 的最长公共子数组的长度。（注意子数组必须以A[i-1]、B[j-1]为结尾）

边界条件：dp[i][j]=0

当时，A[0:i]=A[0:0] 为空，空数组和任何子数组的最长重复子数组的长度都是，因此对任意，有 dp[0][j]=0；
当时，B[0:j]=B[0:0] 为空，同理可得，对任意，有 dp[i][0]=0。

状态转移方程：

当时，将这两个相同的字符称为公共字符，考虑 A[0:i−1] 和 B[0:j−1] 的最长公共子串，再增加一个数，即可得到 A[0:i] 和 B[0:j] 的最长公共子序列，因此 dp[i][j]=dp[i−1][j−1]+1。
当，此时 dp[i][j]=0。

自顶向下（不能用）

因为状态转移方程中，当时，，没有进行递归，所以无法使用自顶向下的方法。

自底向上

自底向上-状态压缩

自底向上-进一步空间优化

转态转移方程如下所示，因为dp[i][j]只与 dp[i-1][j-1]有关，所以可以从右往左添将空间复杂度进行进一步压缩。

72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符

示例 1：输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

题解一

状态：假设单词 word1 和 word2 的长度分别为 m 和 n，创建行列的二维数组 dp，其中 dp[i][j]表示 word1[0:i] 和 word2[0:j] 的编辑距离。（注意子数组必须以 word1[i-1]、word2[j-1]为结尾）

边界条件：一个空串和一个非空串的编辑距离为 dp[i][0] = i 和 dp[0][j] = j，dp[i][0] 相当于对 word1 执行 i 次删除操作，dp[0][j] 相当于对 word1执行 j 次插入操作。

状态转移方程：是左闭右开的二维数組，所以的转移需要判断、

当时，计算
假设 word2=hell。分别使用插入、删除、替换操作，将word1变为word2。
插入操作：比较 word1[0,...,i] 和 word2[0,...,j-1]，如果word1[0,...,i]=word2[0,...,j-1]。那么在word1后面插入word2[j]就可以将word1变为word2。例如word1=hel，插入word[3]=l。此时dp[i][j]=dp[i][j-1]+1
删除操作：比较 word1[0,...,i-1] 和 word2[0,...,j]，如果word1[0,...,i-1]=word2[0,...,j]。那么 word1 删除word1[i]就可以将word1变为word2。例如word1=hello，删除word1[4]=o。此时dp[i][j]=dp[i-1][j]+1
替换操作：比较 word1[0,...,i-1] 和 word2[0,...,j-1]，如果word1[0,...,i-1]=word2[0,...,j-1]。则进行一步替换操作就可以将word1变为word2。例如word1=hely，将y替换成l。此时dp[i][j]=dp[i-1][j-1]+1

自顶向下

自底向上

自底向上-状态压缩

115. 不同的子序列 - 力扣（LeetCode）

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

示例 1：输入：s = "rabbbit", t = "rabbit" 输出：3 解释：如右图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。(上箭头符号 ^ 表示选取的字母)

行:s 列:t	“ “ `空`	R	A	B	B	B	I	T
“ “ `空`	1	1	1	1	1	1	1	1
R	0	1	1	1	1	1	1	1
A	0	0	1	1	1	1	1	1
B	0	0	0	1	2	3	3	3
B	0	0	0	0	1	3	3	3
I	0	0	0	0	0	0	3	3
T	0	0	0	0	0	0	0	3

题解一

状态：假设字符串 s 和 t 的长度分别为 m 和 n，创建行列的二维数组 dp，其中 dp[i][j]表示 s[0:i] 的子序列中 t[0:j] 出现的个数。

边界条件：如果t是空字符串，选取s[0:0]便得到空字符串，所以dp[i][0]=1；如果 s 是空字符串，且t不是空字符串，则 s中的子序列中 t 出现的个数为0，dp[0][j]=0其中。

状态转移方程：如果 s[i-1]=t[j-1]，此时 dp[i][j]为字符串s[0:i-1]中的子序列中 t[0:j-1] 出现的次数 dp[i-1][j-1]+字符串s[0:i-1]中的子序列中 t[0:j] 出现的次数 dp[i-1][j]，例如：s=abcdc、t=ace，dp[4][1]=abcd中出现a的次数+abcd中出现ac的次数=dp[i-1][j-1]+dp[i-1][j]；如果，此时 dp[i][j]为字符串s[0:i-1]中的子序列中 t[0:j] 出现的次数 dp[i-1][j]，例如：s=abcdc、t=ace，dp[3][1]=abc中出现ac的次数=dp[i-1][j]。

自顶向下

自底向上

自底向上-状态压缩

自底向上-进一步空间优化

转态转移方程如下所示，因为dp[i][j]只与 dp[i-1][j-1]、d[i-1][j]有关，所以可以从右往左添将空间复杂度进行进一步压缩。

LC97. Interleaving String

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" 输出：true

题解一

首先如果，那必然不可能由和交错组成。在时，我们可以用动态规划来求解。

状态：我们定义 dp[i,j] 表示的前个元素和的前个元素是否能交错组成的前个元素。

边界条件：如果、、都是空字符串，那么返回Ture。如果为空字符串，那么dp[0][i]=(dp[0][i-1] and s2[i-1]==s3[i-1])；如果为空字符串，那么dp[i][0]=(dp[i-1][0] and s1[i-1]==s3[i-1])。

状态转移方程：如果，那么的前个元素和的前个元素是否能交错组成的前个元素，取决于的前个元素和的前个元素是否能交错组成的前个元素，即此时 dp[i][j] 取决于 dp[i-1, j]，dp[i][j]=dp[i-1, j]；同样的，如果的第个元素和的第个元素相等()，并且dp[i,j−1] 为真，则 dp[i,j] 也为真。于是我们可以推导出这样的动态规划转移方程：

自顶向下

自底向上

自底向上-状态压缩

自底向上-进一步空间优化

转态转移方程如下所示，因为dp[i][j]只与 dp[i-1][j]、dp[i][j-1]有关，所以可以从右往左添将空间复杂度进行进一步压缩。

LC514. Freedom Trail

给定一个字符串 ring，表示刻在外环上的编码；给定另一个字符串 key，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。

最初，ring 的第一个字符与12:00方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。

💡

旋转 ring 拼出 key 字符 key[i] 的阶段中：

您可以将 ring 顺时针或逆时针旋转一个位置，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

示例： 输入: ring = "godding", key = "gd" 输出: 4 解释:
对于 key 的第一个字符 'g'，已经在正确的位置, 我们只需要1步来拼写这个字符。
对于 key 的第二个字符 'd'，我们需要逆时针旋转 ring "godding" 2步使它变成 "ddinggo"。
当然, 我们还需要1步进行拼写。因此最终的输出是 4。

题解一

状态：定义表示从前往后拼写出的第个字符，的第个字符与 12:00 方向对齐的最少步数。同时制作ring的位置信息，记录一下ring中每一个字符的索引值

边界条件：从ring的任意位置转到key[0]，需要的最小步数

💡

ring中每个字符的位置（例如索引i的字符）。顺时针旋转的操作数是i；逆时针旋转的操作数是len(ring)-i

状态转移方程：表示从前往后拼写出的第个字符，的第个字符与 12:00 方向对齐的最少步数；表示从前往后拼写出的第个字符，的第个字符与 12:00 方向对齐的最少步数。计算dp[i][j]就要从ring中所有符合key[i-1]的位置，左旋转或右旋转达到key[i]，所需的最小操作数

表示在当前第个字符与 12:00 方向对齐时第个字符旋转到 12:00 方向并按下拼写的最少步数。
表示从顺时针转到第个字符的步数；表示从逆时针转到第个字符的步数。所以使用表示从转到的步数。前第个字符与 12:00 方向对齐时第个字符
表示中所有等于的索引位置

自顶向下

自底向上

自底向上-状态压缩

含有pos数组的代码不能使用状态压缩，因为并不是每一数组都会遍历到。

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9

每个数字最多使用一次

返回所有可能的有效组合的列表。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

动态规划数组 dp[n][k] 表示 k 个数组成和为n

初始边界：dp[i][1]=[{i}]只是用1个数组成和为i的组合就是i

状态转移方程：dp[nItem][kItem].append(temp)