LeetCode300. 最长递增子序列
题目链接：300. 最长递增子序列 - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列_哔哩哔哩_bilibili
思路：这道题是子序列系列的第一道题，我们这道题的dp[i]的含义是以nums[i]为结尾的最长递增子序列的长度，要给所有的dp[i]初始化为1，然后对dp数组进行以下操作，首先j<i，如果nums[j]<nums[i]，则令dp[i]=max(dp[i],dp[j]+1)。在循环完之后，我们取dp数组中的最大值。
代码：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int len=nums.size();
vector<int>dp(len,1);
for(int i=1;i<len;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]){
dp[i]=max(dp[i],dp[j]+1);
}
}
}
int result=0;
for(int i=0;i<len;i++){
result=max(result,dp[i]);
}
return result;
}
};LeetCode674. 最长连续递增序列
题目链接：674. 最长连续递增序列 - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列_哔哩哔哩_bilibili
思路：和前一道题的区别在于连续，反而思路更简单了。dp[i]的含义依旧是到nums[i]的最长递增子序列，dp[i]都初始化为1，此时只需要比较每个nums[i]>nums[i-1]，如果大于那么就让dp[i]=dp[i-1]+1.最后依旧返回所有dp数组中的最大值。
代码：
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
int len=nums.size();
vector<int>dp(len,1);
for(int i=1;i<len;i++){
if(nums[i]>nums[i-1]){
dp[i]=dp[i-1]+1;
}
}
int result=0;
for(int i=0;i<len;i++){
result=max(result,dp[i]);
}
return result;
}
};LeetCode718. 最长重复子数组
题目链接：718. 最长重复子数组 - 力扣（LeetCode）
文章讲解：代码随想录
视频讲解：动态规划之子序列问题，想清楚DP数组的定义 | LeetCode：718.最长重复子数组_哔哩哔哩_bilibili
思路：这道题的dp[i][j]的定义是结尾为nums1[i-1]和结尾为nums2[j-1]的最长充分子数组，至于为什么是i-1和j-1而不是i和j是因为初始化的时候会方便，直接全部初始化为0就可以，否则需要拿某个数组的第一个数字和第二个数组进行比较，匹配的填入1。递推公式为在nums1[i-1]==nums2[j-1]时，dp[i][j]=dp[i-1][j-1]+1;，最后还是求dp数组中的最大值作为result。
代码：
class Solution {
public:
int findLength(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;
}
}
}
int result=0;
for(int i=1;i<=nums1.size();i++){
for(int j=1;j<=nums2.size();j++){
result=max(result,dp[i][j]);
}
}
return result;
}
};