- 数组或者字符串的子序列问题，是一类常见的中等难度的题目
- 区别与连续子串，子序列元素仅保留了数组本来元素的序列关系，不一定存在连续特性。
- 下面汇总的题目总体上都可以通过动态规划进行求解，且求解方法基本一致
- 从题目描述可以看到求解目标基本为：
- 最长XXX子序列, 计算序列长度
- 子序列数量， 计算满足条件的序列数量
- 从动态规划定义上将，基本可以用以下两种定义来实现：
dp[i][j]表示s[:i]t[:j]的目标情况- dp遍历往往内外循环正向即可
dp[i][j]表示s[i:]t[:j]两串的目标情况或者i~j之间的目标情况- dp遍历往往采用外反内正的循环逻辑
- 如： [LC516.最长回文子序列]
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
class Solution {
public:
bool isSubsequence(string s, string t) {
int n = s.size();
int m = t.size();
if (n > m) return false;
int j = 0;
for (int i = 0; i < m; i++) {
if (t[i] == s[j]) {
j++;
}
}
return j == n;
}
};- 进一步思考： 当子串s特别长时，如何进行快速匹配
- 可以考虑在线性遍历的基础上，类似于KMP算法进行下一个位置记录，提高速度
- 使用伪链表方式，记录每个位置下一个字符的位置(n*26的形式)
- 为了保证结果可靠，在模
class Solution {
public:
bool isSubsequence(string s, string t) {
t.insert(t.begin(), ' '); // 初始化操作，使得后续可以计算起来
int len1 = s.size(), len2 = t.size();
vector<vector<int> > dp(len2 , vector<int>(26, 0));
for (char c = 'a'; c <= 'z'; c++) {
int nextPos = -1; //表示接下来再不会出现该字符
for (int i = len2 - 1; i>= 0; i--) { //为了获得下一个字符的位置，要从后往前
dp[i][c - 'a'] = nextPos;
if (t[i] == c)
nextPos = i; // 更新当前字符的最新位置
}
}
int index = 0;
for (char c : s) {
index = dp[index][c - 'a'];
if (index == -1)
return false;
}
return true;
}
};给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。
输入：s = "rabbbit", t = "rabbit"
输出：3
- 子序列为非连续的字符子串，可以通过动态规划的方式来进行求解：
- 定义
dp[i][j]s串以i-1结尾的子序列和t串以j-1结尾的子序列匹配(子串匹配)的数量 - 如果
s[i-1] == t[j-1]则dp[i][j] = dp[i-1][j-1] + dp[i-1][j]dp[i-1][j]即以子串s[i-1]之前的串与t串进行匹配
- 如果
s[i-1] ！= t[j-1]则dp[i][j] = dp[i-1][j]
- 定义
- 初始化：
dp[i][0] = 1dp[0][0] = 1 - 关键点：
动态规划分析
class Solution {
public:
int numDistinct(string s, string t) {
int n = s.size();
int m = t.size();
int end = n;
vector<vector<long long >> dp(n + 1, vector<long long>(m+1, 0));
for (int i = 0; i <= n; i++) dp[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (s[i-1] == t[j-1]) {
dp[i][j] = (dp[i-1][j] + dp[i-1][j-1]) % INT_MAX;
}
else {
dp[i][j] = dp[i-1][j] % INT_MAX;
}
}
}
return dp[n][m];
}
};- 基于dfs的记忆化搜索，通过所有案例，但超时了。。。
- 从本质上理解： 动态规划是不会重复计算的递归搜索
class Solution {
public:
vector<vector<int>> dp;
int backTrack(string s, int beg, int end, string target, int index) {
//cout << "beg" << beg << "end:" << end << "index " << index << endl;
if (index == target.size()) {
return 1;
}
if (beg > end || index > target.size()) {
return 0;
}
if (dp[beg][index] != -1) {
return dp[beg][index];
}
int ans = 0;
for (int k = beg; k <= end; k++) {
if (s[k] != target[index]) {
continue;
}
else {
if (dp[k + 1][index + 1] == -1)
dp[k+1][index+1] = backTrack(s, k + 1, end, target, index + 1);
ans += dp[k+1][index+1];
}
}
return ans;
}
int numDistinct(string s, string t) {
int n = s.size();
int m = t.size();
int end = n;
dp = vector<vector<int>>(n + 1, vector<int>(m+1, -1));
for (int i = n - 1; i >= 0; i--) {
if (s[i] == t.back()) {
end = n - 1;
}
}
if (end == n) {
return 0;
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (s[i] == t[0]) {
ans+=backTrack(s, i, end, t, 0);
break;
}
}
return ans;
}
};给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。
输入: "sea", "eat"
输出: 2
解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"
- 分析： 仍然可以采用动态规划进行求解：
- 与前面的题目中dp定义相似
dp[i][j]表示 word1前i个元素和word2前j个元素相同所需的最小步数word1[i-1]==word2[j-1]当word1第i个元素和word2第j个元素相同时，所需的最小步数为dp[i][j] = dp[i-1][j-1]word1[i-1]!=word2[j-1]当word1第i个元素和word2第j个元素相同时，所需的最小步数dp[i][j] = min(dp[i-1][j-1] + 2, dp[i-1][j] + 1, dp[i][j-1] + 1)
- 初始化：
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size();
int m = word2.size();
vector<vector<int>> dp(n + 1 ,vector<int>(m + 1));
// init dp[i][0] = i
for (int i = 0; i <= n; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= m; i++) {
dp[0][i] = i;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; 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] + 2, min(dp[i-1][j] + 1, dp[i][j - 1] + 1));
}
}
}
return dp[n][m];
}
};- 空间优化，使用滚动数组进行结果存储，这里使用辅助数组进行当前结果存储，使得代码可读性更好
class Solution {
public:
int minDistance(string word1, string word2) {
int n = word1.size();
int m = word2.size();
vector<int> dp(m + 1);
for (int i = 0; i <= m; i++) {
dp[i] = i;
}
for (int i = 1; i <= n; i++) {
vector<int> temp(m + 1);
temp[0] = i;
for (int j = 1; j <= m; j++) {
if (word1[i-1] == word2[j-1]) {
temp[j] = dp[j-1];
}
else {
temp[j] = min(dp[j-1] + 2, min(dp[j] + 1, temp[j - 1] + 1));
}
}
dp = temp; // extra array for temp
}
return dp[m];
}
};- 基础DP思路
- 状态转移公式
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i] - 初始化：
dp[0]=0 - 最后结果需要从dp中选取最大的值
- 时间复杂度O(n^2), 空间复杂度 O(N)
- 状态转移公式
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 0);
dp[0] = 1;
int ans = 1;
for (int i = 1; i < nums.size(); i++) {
dp[i] = 1;
for (int j = 0; j< i; j++) {
if (nums[j] < nums[i]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(dp[i], ans);
}
return ans;
}
};- 贪心+二分搜索
- 要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
- 基于上面的贪心思路，维护一个数组 d[i]，表示长度为 ii 的最长上升子序列的末尾元素的最小值，用 \textit{len}len 记录目前最长上升子序列的长度，起始时 lenlen 为 11，d[1] = \textit{nums}[0]d[1]=nums[0]
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> tail; // 定义不同长度的子序列的最大尾值
int ans;
tail.push_back(nums[0]);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > tail.back()) {
tail.push_back(nums[i]);
}
else {
int left = 0;
int right = tail.size() - 1;
//cout << 'l' << left << 'r' << right << " "<< nums[i] <<endl;
while(left < right) {
// int mid = left + (right - left)/2;
int mid = (left + right) / 2;
if (tail[mid] < nums[i]) {
left = mid + 1;
} else {
right = mid;
}
}
tail[left] = nums[i];
}
}
return tail.size();
}
};未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度
- 连续序列比非连续的子序列要更容易处理， 直接遍历计数即可
- 注意对边界问题的处理， 每次上升即进行更新，而非出现非增再更新结果，以避免序列本身就单增或者结尾单增的情况
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int n = nums.size();
int beg = 1;
int ans = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
beg++;
ans = max(ans, beg);
}
else {
beg = 1;
//ans = max(ans, beg);
}
}
return ans;
}
};- 教科书式经典dp问题
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串
- 定义
dp[i][j]表示子串text1[0:i）和text2[0:j）的公共子序列的最长长度- 状态转移公式： dp[i][j] = dp[i-1][j-1]+ 1 当text1[i] == text2[j]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 状态转移公式： dp[i][j] = dp[i-1][j-1]+ 1 当text1[i] == text2[j]
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n1 = text1.size();
int n2 = text2.size();
vector<vector<int> > dp(n1 + 1, vector<int>(n2 + 1));
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n1][n2];
}
};两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足满足：
nums1[i] == nums2[j]且绘制的直线不与任何其他连线（非水平线）相交。 返回可以绘制的最大连线数
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
- 问题分析： 最大连线数即需要得到两个数组的最长公共子序列，即两侧的元素都相等(满足不相交定义)
- 那么问题即为[LC1143. 最长公共子序列]问题
- 直接进行dp求解即可
class Solution {
public:
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[n][m];
}
};给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数
- 动态规划解题
- 定义
dp[i][j]表示把word1的前i个字母替换为word2的前j个字母的最少操作数量- 那么动态规划的转移方程为;
dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (w1[i]!=w2[j])- 初始化：
dp[i][0] = i - 根据dp定义，那么我们应该初始化[m+1][n+1]的二维数组，返回dp[m][n]作为最终结果
- 对于特殊情况，即其中一个word为空时，编辑距离为非空word的长度
- 尤其要注意索引的设置
- 取字符串内元素的索引和dp的索引
- 时间复杂度O(N^2) 空间复杂度O(N^2)
class Solution {
public:
int minDistance(string word1, string word2) {
int l1 = word1.size();
int l2 = word2.size();
if (word1.empty())
return l2;
if (word2.empty())
return l1;
vector<vector<int>> dp(l1 + 1, vector<int>(l2 + 1));
for (int i = 1; i< l1 + 1; i++) {
dp[i][0] = i;
}
for (int i = 1; i< l2 + 1; i++) {
dp[0][i] = i;
}
for (int i = 1; i < l1 + 1; i++) {
for (int j = 1; j< l2 + 1; j++) {
int tmp = 1;
// 对于字符串取值，需要注意索引的差异
if (word1[i-1] == word2[j-1])
tmp = 0;
dp[i][j] = min(dp[i-1][j] + 1, min(dp[i][j-1] + 1, dp[i-1][j-1] + tmp));
}
}
return dp[l1][l2];
}
};- 进一步优化空间使用，dp问题的常见优化，将二维数组变为一维数组
- 使用一维数组记录当前行的情况，在遍历的同时进行更新
- 代码易读性大幅下降
class Solution {
public:
int minDistance(string word1, string word2) {
int l1 = word1.size();
int l2 = word2.size();
int prev = 0;
if (word1.empty())
return l2;
if (word2.empty())
return l1;
vector<int> dp((l2 + 1));
for (int i = 0; i < l2 + 1; i++) {
dp[i] = i;// dp[i][j]
}
for (int i = 1; i < l1 + 1; i++) {
prev = dp[0]; // dp[i-1][j-1]
dp[0] = i; // dp[i-1][0] 更新dp赋值
for (int j = 1; j < l2 + 1; j++) {
// dp[i][j] = dp[i-1][j] dp[i][j-1]
// 提前存储上一行的状态，避免被覆盖
int tmp = dp[j];
dp[j] = min(dp[j] + 1, min(dp[j-1] + 1, prev + int(word1[i-1] != word2[j-1])));
prev = tmp;
}
}
return dp.back();
}
};给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。
输入:
"bbbab"
输出:
4 (bbbb)
- 注意：这里是子序列，而不是子串，子串是元素连续的。
- 无法直接采用[LC5.最长回文子串]中简洁的双指针方法
- 需要借助动态规划进行解题
- dp状态定义：
dp[i][j]表示从i元素到j元素之间的最长子序列 - 状态转移：
dp[i][j] = dp[i+1][j-1] + 2, if s[i] == s[j]dp[i][j] = max(dp[i+1][j], dp[i][j-1]), otherwise对比左右两边的长度
- 特殊情况： 对于长度为1的字符串的处理， 通过对
dp[i][i]进行初始化即可 - 遍历方向： 需要保证左下右方向的结果提前计算处理，因此要在外层进行反方向遍历，在内循环正常从i + 1开始遍历，从下往上得到最终结果
- dp状态定义：
- 关键点：
dp初始化遍历方向
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> dp (n, vector<int> (n));
for (int i = n - 1; i >= 0; i--) {
dp[i][i] = 1; // 处理长度为1的特殊情况
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2; // 注意转移公式
}
else {
dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
}
}
}
return dp[0][n-1]; //
}
};给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
- 滑窗方法解题，分别移动A/B，调整两个数组的对齐位置，然后进行同位置元素对比，记录连续重复元素的个数
- 时间复杂度 O(N+M)*min(n,m)
- 空间复杂度 O(1)
class Solution {
public:
int findRepeat(vector<int> A, vector<int> B, int addA, int addB, int len) {
int res = 0;
int k = 0;
// 记录当前遍历下的最优结果
for (int i = 0; i < len; i++) {
if (A[addA + i] == B[addB + i])
k++;
else {
k = 0;
}
res = max(res, k);
}
return res;
}
int findLength(vector<int>& A, vector<int>& B) {
int m = A.size();
int n = B.size();
int ans = 0;
// 左移B数组
// 当结果大于/等于当前对齐长度后break
for (int i = 0; i < n - 1; i++) {
int len = min(m, n - i);
if (ans >= len)
break;
ans = max(findRepeat(A, B, 0, i, len), ans);
}
// 左移A数组
// 当结果大于/等于当前对齐长度后break
for (int i = 0; i < m - 1; i++) {
int len = min(n, m - i);
if (ans >= len)
break;
ans = max(findRepeat(A, B, i, 0, len), ans);
}
return ans;
}
};- 动态规划解法
- 定义
dp[i][j]表示A数组以i开始和B数组以j开始的子串的最大公共长度； dp[i][j] = dp[i+1][j+1] + 1 if dp[i] == dp[j]; otherwise dp[i][j] = 0;- 最终结果为dp数组中的最大值
- 定义
- 时间复杂度
O(M*N)空间复杂度O(M*N)
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
int m = A.size();
int n = B.size();
int ans = 0;
// 多增加一维，便于初始化
vector<vector<int>> dp(m + 1, vector<int> (n + 1));
//反向遍历 更新dp数组
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (A[i] == B[j]) {
dp[i][j] = dp[i + 1][j + 1] + 1;
}
else {
dp[i][j] = 0;
}
ans = max(ans, dp[i][j]);
}
}
return ans;
}
};在编辑距离上的改动：
给定两个字符串str1和str2，再给定三个整数ic，dc，rc，分别代表插入、删除、替换一个字符的代价，返回将str1编辑成str2的最小代价。
- 编辑距离问题中没有涉及到不同方式的代价，都是1；
- 修改状态转移公式：
dp[i][j] = min(dp[i][j-1] + ic, dp[i-1][j] + dc, dp[i-1][j-1] / dp[i-1][j-1] + rc)- 当
str1[i]!=str[j]时， 从str1[i] 转移到 str2[j]需要把[i]/[j]进行替换，所以加上的时rc - 其他ic / dc都是ß本质上考察对状态转移公式的理解
- 状态初始化：
dp[0][j] = ic*jdp[i][0] = dc*i
https://www.it610.com/article/1176869420593655808.htm
- 当
1.dp[0][0]表示空串编辑成空串，故dp[0][0]=0;
2.求第一行dp[0][j]，空串编辑成str2[0….j-1]，则dp[0][j]=ic*j;
3.求第一列dp[i][0]，str1[0……i-1]编辑成空串，则dp[i][0]=dc*i;
4.求dp[i][j]，即str1[0….i-1]编辑成str2[0…..j-1]，四种可能的途径：
<1>str1[0….i-1]先编辑成str2[0…..j-2]，再由str2[0…..j-2]到str2[0…..j-1]，即dp[i][j-1]+ic;
<2>str1[0….i-1]先编辑成str1[0…..i-2]，再由str1[0…..i-2]到str2[0…..j-1]，即dc+dp[i-1][j];
<3>如果str1[i-1]==str2[j-1],则dp[i][j]=dp[i-1][j-1];