【动态规划】（五）动态规划——子序列问题

子序列问题

☆ 最长递增子序列（离散）

力扣链接

• 给定一个整数数组 nums ，找到其中最长严格递增子序列的长度。
• 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,2,2,3]
输出：4

题解：

• 子序列问题是动态规划解决的经典问题，当前下标 i 的递增子序列长度，其实和 i 之前的下标 j 的子序列长度有关系

• 学习参考视频：Leetcode 300 最长递增子序列

动规五部曲
1. 确实dp数组含义： dp[i]表示 i 之前包括 i 的以 nums[i] 结尾的最长递增子序列的长度

2. 确定递推公式：

• 位置 i 的最长升序子序列等于 j 从 0 到 i-1 各个位置的最长升序子序列 + 1 的最大值。

• 相当于由 dp[j] + 1 的最大值形成的子序列（ i 之前的最长子序列）后加上 dp[i] 形成新的最长子序列

• 所以，递推公式为：

  if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
  

• 注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

  

3. dp数组初始化： dp[i] = 1，根据定义，单独一个元素形成的最长递增子序列长度为1

4. 遍历顺序： dp[i] 是有 0 到 i - 1 各个位置的最长递增子序列 推导而来，那么遍历 i 一定是从前向后遍历。

5. 举例推导dp数组： [0,1,0,3,2]，dp数组的变化如下：

 
程序实现：

int lengthOfLIS(vector<int>& nums) 
{// 10,9,2,5,3,7,101,18// 1  1 1 2 2 3  4   4//dp[i]: 表示考虑下标 i 可形成的最长递增子序列长度vector<int> dp(nums.size(),1);dp[0] = 1;for(int i = 1; i < nums.size();i++){for(int j = 0; j < i; j++){// 遍历0-i,在nums[j]小的的dp中取dp的max + 1if(nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1);}}// 求dp数组中的最大值return *max_element(dp.begin(),dp.end());
}

最长连续递增序列（连续）

力扣链接

• 给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

• 连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

思路

• 本题与上题及其相似，唯一区别在于是否连续
• 延续上题思想，对于非延续，j 需要遍历 [0,j)的区间内找最大的dp，而对于延续而言，j 的取值只有 i-1
• 因此递推公式中的 j 改为 i - 1即可，递推公式如下：

  if(nums[i] > nums[i-1])dp[i] = dp[i-1] + 1
  

程序实现：

// 动规
int findLengthOfLCIS(vector<int>& nums) 
{//1,3,5,4,7//1 2 3 3 2//dp[i]: 表示考虑下标 i 可形成的最长连续递增子序列长度vector<int> dp(nums.size(),1);dp[0] = 1;for(int i = 1; i < nums.size();i++){// 连续递增if(nums[i] > nums[i-1])   dp[i] = dp[i-1] + 1;}return *max_element(dp.begin(),dp.end());
}

最大子序和（连续）

力扣链接

• 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6

注：本题也可以用贪心的思想，在贪心章节有涉及： 核心思想是不断累加，加到负数则舍弃之前的累加值（贪心），重新累加，同时在累加过程中记录累加的最大值。

动规五部曲
1. 确实dp数组含义： 包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]。

2. 确定递推公式：

• 取nums[i]：dp[i] = dp[i-1] + nums[i];
• 不取nums[i]：dp[i] = nums[i];
• 递推公式：dp[i] = max(dp[i-1] + nums[i], nums[i]);

3. dp数组初始化： dp[0] = nums[0]; 递推的根基

4. 遍历顺序： 递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。

5. 举例推导dp数组： 以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：

程序实现：

int maxSubArray(vector<int>& nums) 
{// dp[i]：考虑到下标 i 形成的最大子序列数组和// 延续前面的子序列：dp[i-1] + nums[i]// 不延续前面子序列：nums[i]vector<int> dp(nums.size());dp[0] = nums[0];int result = dp[0];for(int i = 1; i < nums.size(); i++){dp[i] = max(dp[i-1] + nums[i], nums[i]);if(dp[i] > result)result = dp[i];	}for(int num : dp)cout << num << " ";return result;
}

最长重复子数组（连续）

力扣链接

• 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组（连续子序列）的长度。

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

注： 本题是上述 【最长连续递增序列】 的二维化（求两个数组的最长公共连续序列），同时又为求最长【 连续公共子序列】（非连续）做了铺垫，属于一道过渡题。

动规五部曲
1. 确实dp数组含义：

• 长度为[0, i - 1]的nums（以下标 i - 1 结束）与长度为[0, j - 1]的nums2（以下标 j - 1 结束）的最长公共子数组长度为dp[i][j]
• 为什么这样定义：简化dp数组第一行和第一列的初始化逻辑，并且接触的程序大多都这样定义

2. 确定递推公式： 比较数组元素是否相同，决定了公共子数组的长度，比较元素就两种情况 ：

• 元素相同： 两个数组单个元素相同，即最长公共子数组长度 = 前面一个（因为连续）最长公共子数组长度 + 1，即：

  if(nums1[i-1] == nums2[j-1])dp[i][j] = dp[i-1][j-1] + 1;
  

  

• 元素不相等： 无重复子数组，dp[i][j] = 0;

3. dp数组初始化：

• dp[i][0]：第一列，无意义，但又是递推公式累加的根基，初始化为 0
• dp[0][j]：第一行，无意义，但又是递推公式累加的根基，初始化为 0
• 其他非0下标初始化可任意值，因为递推时会被覆盖，不妨初始化0

// dp[i][j]: 以 i-1 为结尾的nums1, 以 j -1 为结尾的nums2结尾的最长重复子数组的长度
vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1));
// 第一行 第一列无意义
for(int i = 0; i < nums1.size(); i++)dp[i][0] = 0;
for(int j = 0; j < nums2.size(); j++)dp[0][j] = 0;
int result = 0;

4. 遍历顺序： 根据递推公式，i，j 依靠 i-1，j-1，因此从前向后，从上至下遍历。

for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}if (dp[i][j] > result) result = dp[i][j];}
}

根据dp数组的定义，最终结果为dp[i][j]中最大的元素，因此代码 if (dp[i][j] > result) result = dp[i][j];，即为了实时更新最大值，保存结果。

5. 举例推导dp数组： 拿示例1中，A: [1,2,3,2,1]，B: [3,2,1,4,7]为例，画一个dp数组的状态变化，如下：

程序实现：

//本题是动规解决的经典题目
//用二维数组记录两个字符串的所有比较情况
int findLength(vector<int>& nums1, vector<int>& nums2) 
{// dp[i][j]: 以 i-1 为结尾的nums1, 以 j -1 为结尾的nums2结尾的最长重复子数组的长度vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1));// 第一行 第一列无意义for(int i = 0; i < nums1.size(); i++)dp[i][0] = 0;for(int j = 0; j < nums2.size(); j++)dp[0][j] = 0;int result = 0;for(int i = 1; i <= nums1.size(); i++){for (int j = 1; j <= nums2.size(); j++){// 更新最长公共子数组长度if(nums1[i-1] == nums2[j-1])dp[i][j] = dp[i-1][j-1] + 1;// 记录dp[i][j]最大值if(dp[i][j] > result)result = dp[i][j];}}// 打印dp数组for(int i = 0; i <= nums1.size(); i++){for(int j = 0; j <= nums2.size(); j++)cout << dp[i][j] << " ";cout << endl;}return result;
}

☆ 最长公共子序列（离散-编辑距离过渡）

学习参考视频：[轻松掌握动态规划] 5.最长公共子序列 LCS

力扣链接

• 给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
• 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
• 若这两个字符串没有公共子序列，则返回 0。

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

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• 输入的字符串只含有小写英文字符。

动规五部曲
1. 确实dp数组含义：

• 长度为[0, i - 1]的字符串text1（以下标 i - 1 结束）与长度为[0, j - 1]的字符串text2（以下标 j - 1 结束）的最长公共子序列长度为dp[i][j]

• 为什么这样定义：简化dp数组第一行和第一列的初始化逻辑，并且接触的程序大多都这样定义

2. 确定递推公式： 比较数组元素是否相同，决定了公共子序列的长度，比较元素就两种情况 ：

• 元素相同： 两个数组单个元素相同，即最长公共子序列长度 + 1，即：

  if(text1[i-1] == text2[j-1])dp[i][j] = dp[i-1][j-1] + 1;
  

  

• 不相同

  • 舍弃text1[i-1]，考虑由text1[i-2] 和text2[j-1] 结束形成的最大公共子序列

    dp[i][j] = dp[i-1][j];
    

  
  • 舍弃text2[j-1]，考虑由text1[i-1] 和text2[j-2] 结束形成的最大公共子序列

    dp[i][j] = dp[i][j-1];
    

    
  • 因此当 text1[i-1] == text2[j-1] 不相等时，递归公式为：

    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    

3. dp数组初始化：

• dp[i][0]：text1[0, i-1]和空串的最长公共子序列自然是0，所以 dp[i][0] = 0;

• 同理，dp[0][j] = 0;

• 其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0

  vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
  

4. 遍历顺序： 从递推公式，可以看出，有三个方向可以推出dp[i][j]，如图：

那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。

 
5. 举例推导dp数组： text1 = “ABCBDAB”, text2 = “BDCABC” 为例，dp状态如图：

程序实现

//用二维数组记录两个字符串的所有比较情况
int longestCommonSubsequence(string text1, string text2) 
{// dp[i][j]: 以 i-1 为结尾的 text1, 以 j -1 为结尾的 text2 结尾的最长重复子数组的长度// 长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));// 第一行 第一列无意义 初始化全为 0int result = 0;for(int i = 1; i <= text1.size(); i++){for (int j = 1; j <= text2.size(); j++){// 元素相同if(text1[i-1] == text2[j-1])dp[i][j] = dp[i-1][j-1] + 1;// 元素不相同// dp[i][j-1]：abc 和 考虑ac不考虑e// dp[i-1][j]：考虑ab不考虑c 和 aceelsedp[i][j] = max(dp[i][j-1], dp[i-1][j]);if(dp[i][j] > result)result = dp[i][j];}}
//		for(int i = 0; i <= text1.size(); i++)
//		{
//			for(int j = 0; j <= text2.size(); j++)
//			{
//				cout << dp[i][j] << " ";
//			}
//			cout << endl;
//		}return result;
}

不相交的线（等价最大公共子序列）

力扣链接

• 我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
• 现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。
• 以这种方法绘制线条，并返回我们可以绘制的最大连线数。

示例：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2

示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

题解：

• 拿示例一A = [1,4,2], B = [1,2,4]为例，相交情况如图：

• 其实也就是说A和B的最长公共子序列是[1,4]，长度为2。 这个公共子序列指的是相对顺序不变（即数字4在字符串A中数字1的后面，那么数字4也应该在字符串B数字1的后面）

• 通过分析发现：本题说是求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

• 这与上一题最最长公共子序列的程序完全一致，这里不再赘述。

编辑距离问题

判断子序列

力扣链接

• 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

• 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：
输入：s = “abc”, t = “ahbgdc”
输出：true

示例 2：
输入：s = “axc”, t = “ahbgdc”
输出：false

这道题应该算是编辑距离的入门题目，因为从题意中我们也可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。

所以掌握本题的动态规划解法是对后面要讲解的编辑距离的题目打下基础。

动规五部曲

1. 确实dp数组含义： 由下标 i-1 结束的s, j-1结束的 t 相同子序列的长度为dp[i][j]，其中 s <= t

2. 确定递推公式：

• s[i-1] == t[j-1]： t 中找到了一个字符在 s 中也出现了，此时最长子序列长度 + 1，递推公式即：

  dp[i][j] = dp[i-1][j-1] + 1;
  

  

• s[i-1] != t[j-1]： 相当于 t 要删除元素，继续匹配，t 如果把当前元素t[j - 1]删除，那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了，递推公式即：

  dp[i][j] = dp[i][j-1];
  

  

3. dp数组初始化： dp[i][0] 表示以下标 i-1为结尾的字符串，与空字符串的相同子序列长度，所以为0. dp[0][j]同理。

vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));

4. 遍历顺序： 同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，那么遍历顺序也应该是从上到下，从左到右，如图所示：

5. 举例推导dp数组： 以示例一为例，输入：s = “abc”, t = “ahbgdc”，dp状态转移图如下：

程序实现：

bool isSubsequence(string s, string t) 
{// s <= t// dp[i][j]：由下标 i-1 结束的s, j-1结束的t 相同子序列的长度为dp[i][j]// 类似于最长公共子序列vector<vector<int>> dp(s.size() + 1,vector<int>(t.size() + 1,0));for(int i = 1; i <= s.size(); i++){for(int j = 1; j <= t.size(); j++){if(s[i-1] == t[j-1])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = dp[i][j-1];}}for(int i = 0; i <= s.size(); i++){for(int j = 0; j <= t.size(); j++){cout << dp[i][j] << " ";}cout << endl;}if(dp[s.size()][t.size()] == s.size())return true;elsereturn false;
}

注： 此外本题可以求 s 和 t 的公共子序列长度，若公共子序列长度 == s.size()，那么 s 就是 t 的子序列，否则不是。

不同的子序列

力扣链接

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

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

示例 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  

动规五部曲
1. 确实dp数组含义： 以下标 i-1结尾的s，以下标 j-1结尾的t，s的子序列中，t 出现的个数为 dp[i][j]
2. 确定递推公式：

• s[i - 1] == t[j - 1]

  • 用s[i - 1]来匹配，那么个数为 dp[i - 1][j - 1]。即不需要考虑当前 s 子串和 t 子串的最后一位字母，所以只需要 dp[i-1][j-1]

  • 一部分是不用s[i - 1]来匹配，个数为 dp[i - 1][j]

    

  • Q1：为什么还要考虑 不用s[i - 1]来匹配

  • A1：例如 s：bagg 和 t：bag ，s[3] 和 t[2]是相同的，但是字符串s也可以不用s[3]来匹配，即用s[0]s[1]s[2]组成的bag。

  • Q2：为什么只考虑 “不用s[i - 1]来匹配” 这种情况， 不考虑 “不用t[j - 1]来匹配” 的情况呢

  • A2：我们求的是 s 中有多少个 t，而不是 求 t 中有多少个 s，所以只考虑 s 中删除元素的情况，即 不用s[i - 1]来匹配 的情况。

  • 所以当s[i-1] == t[j-1]时候，递推公式为：

    dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
    

• s[i - 1] != t[j - 1]

  • dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]
    

3. dp数组初始化：

• dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数，dp[i][0] = 1;，因为也就是把以i-1为结尾的s，删除所有元素，出现空字符串的个数就是1
• dp[0][j]：空字符串s可以随便删除元素，出现以j-1为结尾的字符串t的个数，那么dp[0][j]一定都是0，s如论如何也变成不了t。

  vector<vector<long long>> dp(s.size() + 1, vector<long long>(t.size() + 1));
  for (int i = 0; i <= s.size(); i++) dp[i][0] = 1;
  for (int j = 1; j <= t.size(); j++) dp[0][j] = 0; 
  

4. 遍历顺序： 从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的，遍历的时候一定是是从上到下，从左到右

5. 举例推导dp数组： 以s：“baegg”，t："bag"为例，推导dp数组状态如下：

程序实现：

int numDistinct(string s, string t)
{// s >= t// dp[i][j]：由下标 i-1 结束的s, j-1结束的t 子序列出现的个数vector<vector<int>> dp(s.size() + 1,vector<int>(t.size() + 1));for(int i = 0; i <= s.size();i++)dp[i][0] = 1;for(int j = 1; j <= t.size();j++)dp[0][j] = 0;for(int i = 1; i <= s.size(); i++){for(int j = 1; j <= t.size(); j++){if(s[i-1] == t[j-1])dp[i][j] = dp[i-1][j-1] + dp[i-1][j];elsedp[i][j] = dp[i-1][j];}}for(int i = 0; i <= s.size(); i++){    for(int j = 0; j <= t.size(); j++)cout << dp[i][j] << " ";cout << endl;}return dp[s.size()][t.size()];
}

两个字符串的删除操作

力扣链接

• 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：
输入: “sea”, “eat”
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

本题和上题不同的子序列相比，其实就是两个字符串都可以删除了，情况虽说复杂一些，但整体思路是不变的。

直接法

动规五部曲
1. 确实dp数组含义： 以 i-1为结尾的字符串word1，和以 j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数

2. 确定递推公式：

word1[i - 1] == word2[j - 1]，不操作，dp[i][j] = dp[i - 1][j - 1];

word1[i - 1] != word2[j - 1]，

• 删除word1[i-1]，最少操作步骤为：

  dp[i][j] = dp[i - 1][j ] + 1
  

• 删除word2[j-1]，最少操作步骤为：

  dp[i][j] = dp[i ][j-1 ] + 1;
  

• 同时删除word1[i-1]和word2[j-1]，最少操作步骤为：

  dp[i][j] = dp[i -1][j-1 ] + 2;
  

• 所以递推公式为：

  dp[i][j] = min(dp[i - 1][j ] + 1, dp[i][j - 1] + 1, dp[i -1][j-1 ] + 2);
  

• 这里不再画图解释，删除操作参考上述两题的图解

3. dp数组初始化：

• dp[i][0]：word2为空，以i-1为结尾的字符串word1要删除 i 个元素，才和word2相同，因此 dp[i][0] = i
• 同理，dp[0][j] = j;
• 其余位置无需初始化，会通过递推覆盖

4. 遍历顺序： 通过递推公式可得，从上往下，从左往右遍历。

5. 举例推导dp数组： 以word1:“sea”，word2:"eat"为例，推导dp数组状态图如下：

程序实现：

// 动规 直接法
int minDistance(string word1, string word2)
{// dp[i][j]：由下标 i-1 结束的s, j-1结束的t 最少删除dp[i][j]步才能使字符串相等vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1, 0));//初始化for(int i = 0; i <= word1.size();i++)dp[i][0] = i;for(int j = 0; j <= word2.size();j++)dp[0][j] = j;for(int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){// 相等if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1];else	// 不相等dp[i][j] = min(dp[i-1][j] + 1,min(dp[i][j-1] + 1, dp[i-1][j-1] + 2));}}for(int i = 0; i <= word1.size(); i++){    for(int j = 0; j <= word2.size(); j++){cout << dp[i][j] << " ";}cout << endl;}return dp[word1.size()][word2.size()];
}

间接法

• 通过问题分析，需要对两个字符串删除多余的元素，使其变成 word1 = word2，即变成公共子序列。
• 从结果出发，计算两个字符串的最长公共子序列长度n，那么最少需要 word1.size() + word2.size() - 2 * n 就可以使得word1 == word2。

程序实现：

// 动规 求最长公共子序列 算出结果剩下的数组
int minDistance2(string word1, string word2)
{// dp[i][j]：由下标 i-1 结束的s, j-1结束的t组成的最长公共子序列的长度vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1, 0));for(int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return word1.size() + word2.size() - 2 * dp[word1.size()][word2.size()];
}

编辑距离

力扣链接

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

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

示例 2：
输入：word1 = “intention”, word2 = “execution”
输出：5

动规五部曲
1. 确实dp数组含义： dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

2. 确定递推公式：
在确定递推公式的时候，首先要考虑清楚编辑的几种操作，整理如下：

if (word1[i - 1] == word2[j - 1])不操作
if (word1[i - 1] != word2[j - 1])增/删/换

if (word1[i - 1] == word2[j - 1]) ：那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];

if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，

• 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作，即：

  dp[i][j] = dp[i - 1][j] + 1;
  

• 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作

  dp[i][j] = dp[i][j - 1] + 1;
  

• 操作三：替换元素： word1替换word1[i - 1]，使其与word2[j - 1]相同，只需要一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同，即：

  dp[i][j] = dp[i - 1][j - 1] + 1
  

• 所以当 word1[i - 1] != word2[j - 1]时，递推公式为：

  dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1 );
  

3. dp数组初始化：

• dp[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，需要最小编辑的距离才是其相等，因此 dp[i][0] = i;
• 同理，dp[0][j] = j;

4. 遍历顺序： 根据递推公式从左到右从上到下去遍历

 
5. 举例推导dp数组： 以示例1为例，输入：word1 = “horse”, word2 = "ros"为例，dp矩阵状态图如下：

程序实现

// 动规
int minDistance(string word1, string word2)
{// dp[i][j]：由下标 i-1 结束的word1, j-1结束的word2 最少的操作次数为dp[i][j]vector<vector<int>> dp(word1.size() + 1,vector<int>(word2.size() + 1, 0));for(int i = 0; i <= word1.size();i++)dp[i][0] = i;for(int j = 0; j <= word2.size();j++)dp[0][j] = j;for(int i = 1; i <= word1.size(); i++){for(int j = 1; j <= word2.size(); j++){if(word1[i-1] == word2[j-1])dp[i][j] = dp[i-1][j-1];else{//删除word1[i-1]:	dp[i-1][j] + 1    //删除word2[j-1]:	dp[i][j-1] + 1    // 替换 dp[i-1][j-1] + 1 	dp[i][j] = min(dp[i-1][j] + 1,min(dp[i][j-1] + 1, dp[i-1][j-1] + 1 ));}}}for(int i = 0; i <= word1.size(); i++){    for(int j = 0; j <= word2.size(); j++){cout << dp[i][j] << " ";}cout << endl;}return dp[word1.size()][word2.size()];
}

编辑距离总结

编辑距离总结篇

回文问题

回文子串

力扣链接

• 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
• 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：
输入：“abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”

示例 2：
输入：“aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

动规五部曲
1. 确实dp数组含义：
  本题如果定义dp[i] 为下标i结尾的字符串有 dp[i]个回文串的话，我们会发现很难找到递归关系，因为dp[i] 和 dp[i-1]，dp[i + 1] 看上去都没啥关系。

所以我们要看回文串的性质。 如图：

 

判断一个子字符串（字符串下标范围[i,j]）是否回文，依赖于，子字符串（下标范围[i + 1, j - 1]）） 是否是回文串

定义dp[i][j]数组：dp[i][j]表示以i开头，j结尾的字符串（区间[i,j]）是否为回文串，是则 true，否则 false

2. 确定递推公式： 根据上图可知，dp[i][j]依赖于dp[i+1][j-1]，以及比较 s[i]和s[j]是否相等

当s[i]与s[j]不相等，dp[i][j] = false

当s[i]与s[j]相等：

• 情况1：i = j： dp[i][j] = true;
• 情况2：j - i = 1： dp[i][j] = true;，例如 aa
• 情况3：j - i > 1： 取决于dp[i+1][j-1]是否为字符串

  if(dp[i+1][j-1])dp[i][j] = true;
  

3. dp数组初始化： 默认全部非回文串，在遍历中判断哪些是回文串，因此 dp[i][j] = false

4. 遍历顺序： 遍历顺序可有有点讲究了

• 首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。

• dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：
  

• 因此遍历顺序为：从下往上，从左往右，这样保证dp[i + 1][j - 1]都是经过计算的。

5. 举例推导dp数组： 举例，输入：“aaa”，dp[i][j]状态如下，图中有6个true，所以就是有6个回文子串。

程序实现

//动规
int countSubstrings(string s) 
{// dp[i][j]：表示区间范围:[i,j]内的字符串是否为子串vector<vector<bool>> dp(s.size(), vector<bool>(s.size(),false));int result = 0;// s[i] == s[j]		//  i == j 		//相邻：i + 1 = j	dp[i][j] = true     result++// j - i > 1		if(dp[i+1][j-1]) 	dp[i][j] = true    result++// s[i] != s[j]			dp[i][j] = false;		for(int i = s.size() - 1; i >= 0; i--){for(int j = i; j < s.size(); j++){//相等if(s[i] == s[j]){//情况1 + 情况2if(j - i <= 1){dp[i][j] = true;result++;}//情况3else{if(dp[i+1][j-1]){dp[i][j] = true;result++;}}	}}}return result;
}

最长回文子序列

力扣链接

• 给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1:
输入: “bbbab”
输出: 4
一个可能的最长回文子序列为 “bbbb”。

示例 2:
输入:“cbbd”
输出: 2
一个可能的最长回文子序列为 “bb”。

动态规划五部曲
1. dp数组含义： 由区间[i,j]组成的字符串的最长回文子序列长度为dp[i][j]

2. 确定递推公式：

• s[i] == s[j]：dp[i][j] = dp[i+1][j-1] + 2;
  

• s[i] != s[j]：说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

  • 加入s[j]的回文子序列长度为dp[i + 1][j]。

  • 加入s[i]的回文子序列长度为dp[i][j - 1]

    

• 因此递推公式即：

  if (s[i] == s[j])dp[i][j] = dp[i + 1][j - 1] + 2;
  elsedp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  

3. 初始化数组：

• 根据递推公式，i，j两个指针一左一右移动，最终 i == j，则是递推的根基，根据定义，dp[i][i] = 1;

  for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
  

• 其他情况初始化为0，这样在 max时候，dp[i][j]才不会被覆盖

4. 确定遍历顺序： 从递归公式中，可以看出，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，如图：

遍历顺序：从下到上，从左到右，这样才能保证下一行的数据是经过计算的。

5. 举例推导dp数组： 输入s:“cbbd” 为例，dp数组状态如图：

程序实现

//动规
int longestPalindromeSubseq(string s) 
{// dp[i][j]：表示区间范围:[i,j]内的最长回文子序列长度为 dp[i][j]vector<vector<int>> dp(s.size(), vector<int>(s.size(),0));// s[i] == s[j]		dp[i][j] = dp[i+1][j-1] + 2 // s[i] != s[j]			// 加入s[i]		dp[i][j-1]	// 加入s[j]		dp[i+1][j]	// i 和 j 相等的情况下: dp[i][j] = 1for (int i = 0; i < s.size(); i++) dp[i][i] = 1;for(int i = s.size() - 1; i >= 0; i--){for(int j = i + 1; j < s.size(); j++){if(s[i] == s[j])dp[i][j] = dp[i+1][j-1] + 2;elsedp[i][j] = max(dp[i+1][j],dp[i][j-1]);}}for(int i = 0; i < s.size(); i++){for(int j = 0; j < s.size(); j++){cout << dp[i][j] << " ";}cout <<  endl;}return dp[0][s.size()-1];
}