本文记录作者刷题过程中与动态规划的序列相关的题目。
一、序列问题
1、最长递增子序列
300. 最长递增子序列（中等难度）
给定一个未经排序的整数数组 nums ，找到其中严格递增子序列的最长长度，子序列可以不连续。
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
class Solution {
public:
/* 动规经典问题
【状态定义】dp[j]表示以nums[j]结尾的最长上升子序列长度
【状态转移】对于任何的i属于[0,j-1],都有
if (nums[j] > nums[i]) dp[j] = max(dp[j], dp[i] + 1);
【初始状态】每个j对应的dp[j]都至少是1.
*/
int lengthOfLIS(vector<int>& nums) {
if (nums.size() <= 1) return nums.size();
vector<int> dp(nums.size(), 1);
int result = 0;
// 从数组中的第2个数开始遍历,当前遍历数为i
for (int j = 1; j < nums.size(); j++) {
// 遍历数组中的[i,j]
for (int i = 0; i < j; i++) {
if (nums[j] > nums[i]) dp[j] = max(dp[j], dp[i] + 1);
}
result=max(result,dp[j]);// 保存dp数组中的最长的长度
}
return result;
}
};
674. 最长连续递增序列（中等难度）
给定一个未经排序的整数数组 nums ，找到其中严格递增子序列的最长长度，子序列必须连续。
输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
点评
class Solution {
public:
/*动态规划问题
【状态定义】dp[i]表示以j结尾的数组的连续递增的子序列的长度
【状态转移】当nums[i+1]>nums[i]时,dp[i+1]=dp[i]+1
【初始状态】dp[i]=1
*/
int findLengthOfLCIS(vector<int>& nums) {
vector<int> dp(nums.size()+1,1);
int res=1;
for(int i=0;i<nums.size();++i){
if(i+1<nums.size()&&nums[i+1]>nums[i]){
dp[i+1]=dp[i]+1;
res=max(res,dp[i+1]);
}
}
return res;
}
};
2、最长重复子序列
718. 最长重复子数组（中等难度）
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的连续子数组的长度 。
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
点评
class Solution {
public:
/* 连续子序列问题：动态规划
【状态定义】dp[i][j]表示以i-1结尾的nums1和以j-1结尾的nums2的重复子序列的长度
(i和j都从1遍历到结尾)
【状态转移】dp[i][j]由一个方向决定：dp[i-1][j-1]
nums1[i-1]==nums2[j-1]时，dp[i][j]=dp[i-1][j-1]+1
【初始状态】全部初始为0
时间复杂度和空间复杂度为O(nxm)
*/
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
int res=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;
res=max(res,dp[i][j]);
}
}
}
return res;
}
};
1143. 最长公共子序列（中等难度）
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度，如果不存在公共子序列 ，返回 0，公共子序列可以不连续 。
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace" ，它的长度为 3 。
点评
class Solution {
public:
/* 最长重复子序列，子序列不连续
【状态定义】dp[i][j]表示长度为[0,i-1]的字符串text1和长度为[0,j-1]的字符串text2的公共子序列的最长长度
【状态转移】dp[i][j]由三个方向决定：dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]
text1[i-1]==text2[j-1]时，dp[i][j]=dp[i-1][j-1]+1
text1[i-1]!=text2[j-1]时，dp[i][j]=max(dp[i-1][j],dp[i][j-1])
【初始状态】全部初始化为0
*/
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.length()+1,vector<int>(text2.length()+1,0));
for(int i=1;i<=text1.length();++i){
for(int j=1;j<=text2.length();++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[text1.length()][text2.length()];
}
};
1035. 不相交的线（中等难度）
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
当nums1[i] == nums2[j]时可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，同时要求该直线不能相交，即每个数字只能属于一条连线
以这种方法绘制线条，返回可以绘制的最大连线数。
nums1 = [1,4,2], nums2 = [1,2,4] 输出：2 解释：可以画出两条不交叉的线，如上图所示。 但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。
class Solution {
public:
/*本题本质上就是求nums1和nums2的最长重复子序列的长度，子序列可以不连续
【状态定义】dp[i][j]表示长度为[0,i-1]的字符串nums1和长度为[0,j-1]的字符串nums2的公共子序列的最长长度
【状态转移】dp[i][j]由三个方向决定：dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]
nums1[i-1]==nums2[j-1]时，dp[i][j]=dp[i-1][j-1]+1
nums1[i-1]!=nums2[j-1]时，dp[i][j]=max(dp[i-1][j],dp[i][j-1])
【初始状态】全部初始化为0
*/
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,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;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[nums1.size()][nums2.size()];
}
};
583. 两个字符串的删除操作（中等难度）
给定两个单词 word1 和 word2 ，每步 可以删除任意一个字符串中的一个字符。返回使得 word1 和 word2 相同所需的最小步数。
输入: word1 = “sea”, word2 = “eat” 输出: 2 解释: 第一步将 “sea” 变为 “ea” ，第二步将 “eat “变为 “ea”
点评
class Solution {
public:
/* 本题和1143题目接近：
求出两个字符串的最长重复子序列的长度，那么除了公共子序列剩余的字符都是要删除的
【状态定义】dp[i][j]表示长度为[0,i-1]的字符串text1和长度为[0,j-1]的字符串text2的公共子序列的最长长度
【状态转换】dp[i][j]由三个方向决定：dp[i-1][j-1]、dp[i-1][j]、dp[i][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]=max(dp[i-1][j],dp[i][j-1])
【初始状态】全部初始化为0
*/
int minDistance(string word1, string word2) {
// 计算最长公共子序列的长度
vector<vector<int>> dp(word1.length()+1,vector<int>(word2.length()+1,0));
for(int i=1;i<=word1.length();++i){
for(int j=1;j<=word2.length();++j){
if(word1[i-1]==word2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
int max_len=dp[word1.length()][word2.length()];
return word1.length()-max_len+word2.length()-max_len;
}
};
3、最大子序列和
剑指 Offer 42. 连续子数组的最大和（简单难度）
53. 最大子数组和（简单难度）
给定一个整数数组 nums ，请返回其中连续子数组的最大和（子数组最少包含一个元素）。
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
点评
class Solution {
public:
/* 最大和子序列问题，子序列必须连续,原始序列中可能存在负值
【状态定义】dp[i]表示以nums[i]结尾的连续子序列的最大和
【状态转移】dp[i]由1个方向决定：dp[i-1],其变化决定于nums[i-1]
共有三种可能：dp[i-1]（放弃累加nums[i]）、dp[i-1]+nums[i]（直接累加nums[i]）、nums[i]（从i开始重新累加）
因为是连续序列，所以排除dp[i-1]，如果放弃累加nums[i]，那么就得从nums[i]重新开始
dp[i]=max(dp[i-1]+nums[i],nums[i])
【初始状态】dp[0]=nums[0],因为取最大值，dp[i]的初始值应该尽可能小，至于有多小，可以取nums[0]或INT_MIN
*/
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size()+1,INT_MIN);
dp[0] = nums[0];
int res = dp[0];
for(int i=1;i<nums.size();++i){
dp[i]=max(nums[i],dp[i-1]+nums[i]);
res=max(res, dp[i]);
}
return res;
}
};
4、编辑距离
392. 判断子序列（简单难度）
给定字符串 s 和 t ，两个字符串都由小写字母组成，判断 s 是否为 t 的子序列，本题中的s可以是不连续的子序列。
输入：s = "abc", t = "ahbgdc"
输出：true
点评
class Solution {
public:
/* 子序列判断，子序列可以不连续
该题可以转换为求s和t的重复子序列的长度，最后判断这个长度是否等于s的长度即可
【状态定义】 dp[i][j]表示以s[i-1]结尾的字符串s和t[i-1]结尾的字符串t的重复子序列的长度
【状态转换】dp[i][j]可以由2个方向推导而来：dp[i-1][j-1]、dp[i][j - 1]
因为s是不连续的子序列，所以s不需要向前回退，t是原序列，可以跳过某些字符不能由dp[i-1][j]推导而来
s[i-1]==t[i-1]时，t中找到了s对应的字符，dp[i][j] = dp[i-1][j-1] + 1
s[i-1]!=t[i-1]时，t中没有找到了s对应的字符，dp[i][j] = dp[i][j - 1]
【初始状态】全部初始化为0
*/
bool isSubsequence(string s, string t) {
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;
else dp[i][j] = dp[i][j - 1];
}
}
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
cout<<dp[i][j];
}
cout<<endl;
}
if (dp[s.size()][t.size()] == s.size()) return true;
return false;
}
};
115. 不同的子序列（困难难度）
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数，s的子序列可以是不连续的。
输入：s = “rabbbit”, t = “rabbit” 输出：3 解释： 如下图所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。 rabbbit rabbbit rabbbit
点评
class Solution {
public:
/* s的不连续子序列中，可以得到t的个数
【状态定义】dp[i][j]表示以i-1为结尾的s子序列中随便删除元素，出现以j-1为结尾的t的个数为dp[i][j]。
【状态转换】假设dp[i][j] 就是s[i] 和t[j] 索引的元素子序列数量，则状态方程是：
s[i] == t[j] 时 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
s[i] != t[j] 时 dp[i][j] = dp[i-1][j]
现在解释
(1)s[i] == t[j] 时，以s="rara" t = "ra" 为例，当i = 3, j = 1时，s[i] == t[j]。
此时分为2种情况，s串用最后一位的a + 不用最后一位的a。
如果用s串最后一位的a,那么t串最后一位的a也被消耗掉，此时的子序列其实=dp[i-1][j-1]
如果不用s串最后一位的a，那就得看"rar"里面是否有"ra"子序列的了，就是dp[i-1][j]
所以 dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
(2)s[i] != t[j] 比如 s = "rarb" t = "ra" 还是当i = 3, j = 1时，s[i] != t[j]
此时显然最后的b想用也用不上啊。所以只能指望前面的"rar"里面是否有能匹配"ra"的
所以此时dp[i][j] = dp[i-1][j]
【初始状态】从递归公式中可知dp[i][0] 和dp[0][j]是必须初始化的
dp[i][0]表示以i-1为结尾的s可以随便删除元素，出现空字符串的情况个数，其结果一定是1，即删除所有元素
dp[0][j]表示以-1为结尾的s可以随便删除元素，出现以j-1为结尾t的情况个数，其结果一定是0
dp[0][0]表示以-1为结尾的s可以随便删除元素，出现空字符串的情况个数，其结果是1
*/
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(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];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[s.size()][t.size()];
}
};
72. 编辑距离（困难难度）
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符 删除一个字符 替换一个字符
示例 1：
输入：word1 = “horse”, word2 = “ros” 输出：3 解释： horse -> rorse (将 ‘h’ 替换为 ‘r’) rorse -> rose (删除 ‘r’) rose -> ros (删除 ‘e’)
点评
class Solution {
public:
/*
【状态定义】dp[i][j]表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2的最近编辑距离。
【状态转移】dp[i][j]是由dp[i-1][j-1]、dp[i - 1][j]、dp[i][j - 1]三个方向推导而来
具体取决于s1[i-1]和s2[i-1]的关系：
s1[i-1]==s2[i-1]时，在s1[i-2]和s2[i-2]后面分别添加一个相同的字符，不需要操作，所以dp[i][j]=dp[i-1][j-1]
s1[i-1]!=s2[i-1]时，增删换三选一,取最小值
（1）尝试删除s1的一个字符：dp[i][j]=dp[i-1][j]+1:以下标i-2为结尾的s1与j-1为结尾的s2的最近编辑距离 再加上一个操作
（2）尝试删除s2的一个字符：dp[i][j]=dp[i][j-1]+1：以下标i-2为结尾的s2与j-1为结尾的s1的最近编辑距离 再加上一个操作
（3）尝试替换s1或者s2的一个字符：替换s1[i-1]或者s2[i-1]使其s1[i-1]==s2[i-1]
dp[i][j]=dp[i-1][j-1]+1：以下标i-2为结尾的s1与j-2为结尾的s2的最近编辑距离 再加上一个操作
取最小：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
【初始状态】
dp[i][0]表示以下标i-1为结尾的字符串word1和以下标0-1为结尾的字符串word2的最近编辑距离，其值是i
dp[0][j]表示以下标0-1为结尾的字符串word1和以下标j-1为结尾的字符串word2的最近编辑距离，其值是j
*/
int minDistance(string s1, string s2) {
vector<vector<int>> dp(s1.length()+1,vector<int>(s2.length()+1,0));
for(int i=0;i<=s1.length();++i) dp[i][0]=i;
for(int j=0;j<=s2.length();++j) dp[0][j]=j;
// 遍历两个字符串
for (int i = 1; i <= s1.size(); i++) {
for (int j = 1; j <= s2.size(); j++) {
// 如果相等，不操作
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
// 如果不相等，分别尝试增删换，取最小值
else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
}
}
return dp[s1.size()][s2.size()];
}
};
5、回文子串
647. 回文子串（中等难度）
给定一个字符串 s ，请返回这个字符串中回文子串的数目，本题中的回文子串是正着读和倒过来读一样的字符串，且由原字符串s中的连续字符组成。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
点评
方法一：暴力破解法（时间复杂度为O(n^3)）
//方法一：暴力获取所有子串
int countSubstrings(string s) {
int res=0;
// 遍历所有的起始位置
for (int i = 0; i < s.length(); ++i) {
// 遍历所有的终止位置
for (int j = i; j < s.length(); ++j) {
//判断子串[i,j]是否是回文串
if (isHui(s.substr(i, j - i + 1)))res++;
}
}
return res;
}
bool isHui(string s){
int left=0;
int right=s.length()-1;
while(left<right){
if(s[left]!=s[right]){
return false;
}
else{
left++;
right--;
}
}
return true;
}
方法二：动态规划法（时间复杂度为O(n^2)，空间复杂度为O(n^2)）
class Solution {
public:
/* 回文子串，子串必须连续
【状态定义】dp[i][j]表示字符串s在[i,j]上是否是回文子串(左右都是闭区间)
【遍历顺序】对i是从大向小遍历，对j是从小向大遍历，则i相当于右指针，j相当于左指针
【状态转移】
子串长度为1，如a。这样的子串是回文子串
子串长度为2，如aa，这样的子串要判断前后端是否相同，即s[i] == s[j]，相同则是回文子串，不相同则不是
故有s[i]== s[j]&&j-i<=1为true时,dp[i][j] = true;
子串长度大于2。比如 ababa 这个字符记作串1，把两边的a去掉，也就是bab记作串2，
可以看出只要串2是一个回文串，那么左右各多了一个a的串1必定也是回文串。
所以当s[i]==s[j]时，自然要看dp[i+1][j-1]是不是一个回文串。
故有s[i]== s[j]&&dp[i+ 1][j-1]为true时,dp[i][j] = true;
【初始状态】全为true或者false都可以
*/
int countSubstrings1(string s) {
vector<vector<bool>>dp (s.size() + 1, vector<bool>(s.size() + 1, false));
int res = 0;
// 右指针i从大到小遍历
for (int i=s.size()-1; i >= 0; i--) {
// 左指针j从小到大遍历
for (int j=i; j<s.size(); j++) {
// 如果区间[i,j]的长度<=2，s[i]==s[j]
if(s[i]==s[j]&&j-i<=1){
res++;
dp[i][j] = true;
}
// 如果区间[i,j]的长度>2,s[i]==s[j]且dp[i+1][j-1]为真
else if(s[i]==s[j]&&dp[i+1][j-1]){
res++;
dp[i][j] = true;
}
}
}
return res;
}
};
方法三：双指针法（时间复杂度为O(n^2)，空间复杂度为O(1)）
/*
首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。
在遍历中心点的时候，要注意中心点有两种情况。
一个元素可以作为中心点，两个元素也可以作为中心点。
*/
int countSubstrings(string s) {
int res = 0;
// 遍历字符串s的每个字符，分别以其为中心进行扩散，
for (int i=0; i<s.size(); i++) {
res += extend(s, i, i, s.size()); // 以i为中心
res += extend(s, i, i + 1, s.size()); // 以i和i+1为中心
}
return res;
}
// 从字符串s的位置i和j分别向两端扩散，
int extend(string& s, int left, int right, int n) {
int res=0;
// 如果left和right扩散后仍然没有出界并且指的字符相等，
while(left>=0&&right<n&&s[left]==s[right]) {
left--;
right++;
res++;
}
return res;
}
5. 最长回文子串（中等难度）
给你一个字符串 s，找到 s 中最长的回文子串，如果有多个最长回文子串，随意输出一个即可。
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
点评
本题和647的代码高度相同。
class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool>>dp (s.size() + 1, vector<bool>(s.size() + 1, false));
string res;
int maxLen = 0;
// 右指针i从大到小遍历
for (int i=s.size()-1; i >= 0; i--) {
// 左指针j从小到大遍历
for (int j=i; j<s.size(); j++) {
// 如果区间[i,j]的长度<=2，s[i]==s[j]
if(s[i]==s[j]){
if(j-i<=1||dp[i+1][j-1]){
dp[i][j] = true;
int len=j-i+1;
if(len>maxLen) {
maxLen=len;
res=s.substr(i,len);
}
}
}
}
}
return res;
}
};
516. 最长回文子序列（中等难度）
给你一个字符串 s ，返回其中最长的回文子序列，注意，本题中的回文子序列可以在字符串s中不连续。
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
点评
class Solution {
public:
/* 动态规划法：回文子串，子串不连续
【状态定义】字符串s在[i,j]范围内最长的回文子序列的长度为dp[i][j]。
【状态转换】要求dp[i][j]就考虑s[i]与s[j]
i==j时,dp[i][j]=1
i!=j时,
s[i]==s[j]时,看中间回文长度可以直接拼接两边,dp[i][j]=dp[i+1][j-1]+2;
s[i]!=s[j]时,必定要舍弃其中一个字母,看舍弃哪个最后长度会更大
dp[i][j]=max(dp[i+1][j], dp[i][j-1]);
【初始状态】初始化dp[i][i]=1,其他为0，递归公式无法计算i和j相同的情况，需要手动初始化
【遍历顺序】先i后j,i倒序,j正序(dp[i][j]=dp[i+1][j-1]说明,i+1在i之前计算,j-1在j之前计算)
【返回形式】返回dp[0][len-1]
*/
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
//for (int i=0; i<s.size(); i++) dp[i][i]=1;
// 遍历dp
for (int i=s.size()-1; i>= 0; i--) {
for (int j=i; j<s.size(); j++) {
if(i==j){
dp[i][j]=1;
}
else if (s[i]==s[j]) {
dp[i][j]=dp[i+1][j-1]+2;
} else {
dp[i][j]=max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][s.size()-1];
}
};