思路：
动规五部曲：
1.确定dp数组及其下标的含义：
dp[i]: 以下标i为结尾的数组的连续递增的子序列长度为dp[i]。
注意这里定义，一定是以下标i为结尾，并不是一定以下标0为起始位置
2.确定递推公式：
如果nums[i+1]>nums[i],那么以i+1结尾的数组的连续递增子序列长度一定等于以i为结尾的数组的连续递增的子序列长度+1
3.初始化：全部初始化为1
4.遍历顺序从前往后遍历
class Solution {
public:
int findLengthOfLCIS(vector& nums) {
if (nums.size() == 0) return 0;
int result = 1;
vector dp(nums.size() ,1);
for (int i = 0; i < nums.size() - 1; i++) {
if (nums[i + 1] > nums[i]) { // 连续记录
dp[i + 1] = dp[i] + 1;
}
if (dp[i + 1] > result) result = dp[i + 1];
}
return result;
}
};
思路：
注意题目中说的子数组，就是连续子序列，这种问题动规最拿手，动规五部曲：
1.确定dp数组以及下标的含义：
dp[i][j]:以下标i-1为结尾的A,和以下标j-1为结尾的B，最长重复子数组长度为dp[i][j].(特别注意：以下标i-1为结尾的A,标明一定是以A[i-1]为结尾的字符串。
此时细心的同学发现，那dp[0][0]是什么含义？其实dp[i][j]的定义就决定着，我们遍历dp[i][j]的时候i和j都要从1开始。
2.确定递推公式：
根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i-1][j-1]推导出来。
当A[i-1]和B[j-1]相等的时候，dp[i][j]=dp[i-1][j-1]+1;
根据递推公式可以看出，遍历i和j要从1开始。
3.dp数组如何初始化
根据dp[i][j]的定义，dp[i][0]和dp[0][j]其实没有意义
但dp[i][0]和dp[0][j]要初始化，因为为了方便递推公式dp[i][j]=dp[i-1][j-1]+1
所以dp[i][0]和dp[0][j]初始化为0.
4.遍历顺序
class Solution {
public:
int findLength(vector& A, vector& B) {
vector> dp (A.size() + 1, vector(B.size() + 1, 0));
int result = 0;
for (int i = 1; i result) result = dp[i][j];
}
}
return result;
}
};
思路：
这道题和上一道题很像，唯一的区别在于上一道题是求连续的相同子序列，但是这道题求的不是绝对连续的，而是求的是相对连续的。
动规五部曲：
1.dp[i][j]及其下标的含义：长度为[0,i-1]的字符串text1与长度为[0,j-1]的字符串text2的最长公共子序列为dp[i][j]。
2.确定递推公式
主要就是两种情况：text1[i-1]==text2[j-1]，text[i-1]与text2[j-1]不同
如果相同，找到一个公共元素，所以dp[i][j]=dp[i-1][j-1]+1;
如果不相同，text1[0,i-2]与text[0,j-1]的最长公共子序列和text1[0,i-1]与text2[0，j-2]的最长公共子序列，取最大。
3.初始化：全部初始化为0，如果没有公共的情况就是0
4.遍历顺序：从前往后遍历
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector> dp(text1.size() + 1, vector(text2.size() + 1, 0));
for (int i = 1; i
Original: https://blog.csdn.net/weixin_64200950/article/details/127815106
Author: 非常的
Title: 代码随想录算法训练营day52||674. 最长连续递增序列||718. 最长重复子数组||1143.最长公共子序列
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/660739/
转载文章受原作者版权保护。转载请注明原作者出处！