主要包含子序列问题及总结
对应leetcode题目为392.115.583.72.647.516
代码地址https://github.com/Ltd5552/Algorithm/tree/master/8-DP/Sequence
编辑距离问题
- dp数组定义：需要特别注意dp定义是什么，是以某一个下标结尾（包含下标对应字符）的还是其中整体最大/小的
- 递推公式：对于编辑距离而言确定好有哪些改变状态的操作即可，注意对于某些情况是否可以合并(增和删)
- 注意初始化：有的可能默认0即可，但有的初始情况得是初始情况的计算结果
392.判断子序列
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
分析
判断是否是子序列，但要注意谁是目标子序列，对于原字符串来说这里就只包含了删除操作——不匹配就删除
这里的删除其实就是不考虑那个了，这里没有那么形象，在真正的编辑距离问题上更好理解删除的含义
递推如下，相等的时候就是匹配上了，从前面的+1即可；不相等就是没匹配上，不考虑或者说跳过这个j即可（也就是后面的删除），由于i是目标子序列的，j是原字符串的，所以就删j（因为是在t[j]中不断找s[i]）
if s[i-1] == t[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = dp[i][j-1]
}
其实就相当于求最长公共子序列，最后判断这个子序列的长度是否等于s的长度，或者说是判断两串的相同子序列长度是否等于s本身。
dp[i][j] 定义为以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度。
func isSubsequence(s string, t string) bool {
dp := make([][]int, len(s)+1)
for i := range dp {
dp[i] = make([]int, len(t)+1)
}
for i := 1; i <= len(s); i++ {
for j := 1; j <= len(t); j++ {
if s[i-1] == t[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = dp[i][j-1]
}
}
}
return dp[len(s)][len(t)] == len(s)
}
为什么最后是使用dp[len(s)][len(t)]来判等，根据dp的定义显然最后求的就是两串的相同子序列长度，用这个长度与s比较如果相等说明相同子序列就是s，反之亦然。
115.不同的子序列
给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag
分析
相对上一个，这道题更进一步了——由“判断有没有”到“有多少个”。
首先定义dp[i][j]为以i-1为结尾的s子序列中出现以j-1为结尾的t的个数。
这里对于相等的情况有了两种操作，一是选取，一是不选（不选的理由是后面可能还存在相等的，机会留给后面的），而两种情况都有可能所以是相加（dp数组是出现次数）
对于不相等的情况就不考虑这个了（删除），注意是不考虑原字符串里的那个
if s[i-1] == t[j-1] {
//dp[i-1][j]相当于是对s[i]进行删除操作
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
} else {
//不匹配就直接删除了（沿用上一次的）
dp[i][j] = dp[i-1][j]
}
dp显然是一个累加的情况，所以dp最后的一个最大
代码
func numDistinct(s string, t string) int {
dp := make([][]int, len(s)+1)
for i := range dp {
dp[i] = make([]int, len(t)+1)
}
for i := range dp {
dp[i][0] = 1
}
for i := 1; i <= len(s); i++ {
for j := 1; j <= len(t); j++ {
if s[i-1] == t[j-1] {
//dp[i-1][j]相当于是对s[i]进行删除操作
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
} else {
//不匹配就直接删除了（沿用上一次的）
dp[i][j] = dp[i-1][j]
}
}
}
return dp[len(s)][len(t)]
}
583.两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。
示例 1：
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"
示例 2:
输入：word1 = "leetcode", word2 = "etco"
输出：4
法一：找删除的部分
经过上面两道题，删除操作就不那么抽象了，这里也是直接提出“删除”这个概念，求的是需要两个串删除的最小次数
而与上一题(115)不一样的在于两个串都可能被“删除”了，而不是某一个里去找另一个
由于是直接问的删除最小次数，那么当相等的情况就无需删除；对于不相等的情况存在三种不同的删除操作
- 删除word1的
- 删除word2的
- 同时删除两串的
在三者里选择最少的即可
//相等的时候word1[i]和word2[j]无需删除操作
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
//删除word1或word2或都删除
dp[i][j] = Min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+2)
}
其实第三种可以省去，因为都删可以由单独删除推导回去(dp[i-1][j]+1)->(dp[i-1][j-1]+1)或是(dp[i][j-1]+1)->(dp[i-1][j-1]+1)
//相等的时候word1[i]和word2[j]无需删除操作
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
//删除word1或word2
dp[i][j] = Min(dp[i][j-1]+1, dp[i-1][j]+1)
}
还要注意初始化是考虑删除次数，若其中一个为空串，一个不为空，那么就是把不为空的删到空为止，所以删除次数就是长度。
// 删除的思路
func minDistance(word1 string, word2 string) int {
//dp数组的定义是到达相等需要删除的最少次数
dp := make([][]int, len(word1)+1)
//初始化为i，因为当其中一个为0的时候另一个都需要完全删除自己(i)
for i := range dp {
dp[i] = make([]int, len(word2)+1)
dp[i][0] = i
}
//同理，注意这里是对每列进行初始化，使用第一行
for i := range dp[0] {
dp[0][i] = i
}
for i := 1; i <= len(word1); i++ {
for j := 1; j <= len(word2); j++ {
//相等的时候word1[i]和word2[j]无需删除操作
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
//删除1/2/都删除
// 执行耗时:4 ms,击败了86.01% 的Go用户
// 内存消耗:6.6 MB,击败了42.49% 的Go用户
//dp[i][j] = utils.Min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+2)
//执行耗时:4 ms,击败了86.01% 的Go用户
//内存消耗:6.6 MB,击败了75.06% 的Go用户
dp[i][j] = utils.Min(dp[i][j-1]+1, dp[i-1][j]+1)
}
}
}
return dp[len(word1)][len(word2)]
}
法二：找不删除的部分
这道题还有一种解法是求出最长公共子序列s，两串删除不是s的部分就是最少需要删除的了
具体操作和最长公共子序列完全一样，只是最后返回结果不同
// 执行耗时:12 ms,击败了17.56% 的Go用户
// 内存消耗:6.6 MB,击败了75.06% 的Go用户
// 最长公共子序列思路：找出最长公共子序列s，两串删除不是s的部分就是最少需要删除的了
// 所以最后结果是word1+word2-2*s（均代表长度）
func minDistanceII(word1 string, word2 string) int {
//dp[i][j]定义为以i-1结尾的A和以j-1结尾的B的最长公共子序列长度
dp := make([][]int, len(word1)+1)
//初始化为i，因为当其中一个为0的时候另一个都需要完全删除自己(i)
for i := range dp {
dp[i] = make([]int, len(word2)+1)
}
for i := 1; i <= len(word1); i++ {
for j := 1; j <= len(word2); j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = utils.Max(dp[i-1][j], dp[i][j-1])
}
}
}
return len(word1) + len(word2) - 2*dp[len(word1)][len(word2)]
}
72.编辑距离
分析
最后就是编辑距离本体，对删除操作有了三道题的铺垫这道题也就比较简单了，这里包含增加、删除、替换三种操作，求达到相等需要的最少编辑次数
相等的情况还是无需任何编辑操作，直接使用之前的就行
不相等的情况就涉及增删换三种不同方式
-
增加和删除的操作次数是一样的（一个增就相当于另一个减，反正结果是要使两个相等）
-
至于替换操作理解是在不相等的基础上只需要一次替换操作就能够相等，所以就是
dp[i-1][j-1]+1
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
//dp[i-1][j-1]+1表示替换操作, dp[i-1][j]+1和dp[i][j-1]+1分别表示(对i删除/对j增加)和(对j删除/对i增加)
dp[i][j] = Min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
}
代码
func minDistanceIII(word1 string, word2 string) int {
dp := make([][]int, len(word1)+1)
//初始化不论是插入、删除还是替换都需要i步操作
for i := range dp {
dp[i] = make([]int, len(word2)+1)
dp[i][0] = i
}
for i := range dp[0] {
dp[0][i] = i
}
for i := 1; i <= len(word1); i++ {
for j := 1; j <= len(word2); j++ {
if word1[i-1] == word2[j-1] {
dp[i][j] = dp[i-1][j-1]
} else {
//dp[i-1][j-1]+1表示替换操作, dp[i-1][j]+1和dp[i][j-1]+1分别表示(对i删除/对j增加)和(对j删除/对i增加)
dp[i][j] = utils.Min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
}
}
}
return dp[len(word1)][len(word2)]
}
回文问题
647.回文子串
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
分析
由于回文两边都需要考虑，所以单用一维dp数组并不能很好的表示过程，而且如果仅用一维dp数组递推关系很难分析。回文串其实是很好想到左右指针，用左右指针分别框定左右进行判断，但也需要判断边界更窄的情况，这就涉及子问题了，所以这里使用动态规划的话可以将dp定义为二维的，利用dp[i][j]来表示[i, j]的这一区间内的字串是否是回文的，这里的i、j就像左右指针，而递推来源就是范围更小一点的子问题：dp[i+1][j-1]
首先对dp[i][j]的定义是以i开始以j结束的串是否是回文的，这里设定为bool类型，true代表回文，false代表不是回文
对于递推公式，由两种情况决定，一是s[i] = s[j]，一是s[i] != s[j]。
s[i] != s[j]，这种情况显然不满足条件，以i和j为边界的子串一定不是回文的，所以dp[i][j] = falses[i] = s[j]，这种情况满足回文要求，但相对更复杂- 当i和j相等的时候那么就只有一个字符，此时是回文的
- 当i和j相差1的时候，比如"aa"，那么此时也是回文的
- 剩下情况串的长度大于等于3，所以还需要看内部的子串是否满足，所以是由
dp[i+1][j-1]推出
代码
func countSubstrings(s string) int {
dp := make([][]bool, len(s))
for i := range dp {
dp[i] = make([]bool, len(s))
}
ans := 0
//从左下到右上，所以是从下往上，从左到右的顺序
for i := len(s) - 1; i >= 0; i-- {
for j := i; j < len(s); j++ {
if s[i] == s[j] {
//"a"和"aa"两种情况
if j-i <= 1 {
ans++
dp[i][j] = true
//这里依赖左下的数据
} else if dp[i+1][j-1] {
ans++
dp[i][j] = true
}
}
}
}
return ans
}
由于依赖子问题的特殊性，这里的遍历方向有了一定的变化，因为子问题是dp[i+1][j-1]，在二维数组中的左下角，所以为了确保左下角的能被先行计算出来，这里从下往上、从左往右遍历，使得子问题计算过。
516.最长回文子序列
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
分析
有了上一题的推导，求回文子序列就不那么难入手了。
这里是求最长回文子序列的长度，所以定义dp[i][j]为在[i, j]范围内最长回文子序列的长度。
当s[i] = s[j]，那么dp[i][j] = dp[i+1][j-1] + 2（和上面的编辑距离有点相似）
当s[i] != s[j]，那么dp[i][j]可以从dp[i+1][j]和dp[i][j-1]中推出（也相当于编辑问题里的删除）
遍历顺序还是和上一题差不多，从下往上，从左往右
func longestPalindromeSubseq(s string) int {
//dp[i][j]是[i,j]范围内最长的回文子序列长度
dp := make([][]int, len(s))
for i := range dp {
dp[i] = make([]int, len(s))
dp[i][i] = 1
}
for i := len(s) - 1; i >= 0; i-- {
for j := i + 1; j < len(s); j++ {
if s[i] == s[j] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
//不相等就看分别加入的情况
dp[i][j] = utils.Max(dp[i+1][j], dp[i][j-1])
}
}
}
return dp[0][len(s)-1]
}