代码随想录训练营Day 56|力扣300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
1.最长递增子序列
视频讲解：动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列_哔哩哔哩_bilibili
代码随想录
代码：
class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(),1);// dp[i]表示以下标i结尾包括i的最长递增子序列的长度int result = 1;for(int i = 1; i < nums.size(); i++){for(int j = 0; j < i; j++){if(nums[i] > nums[j]){dp[i] = max(dp[j] + 1,dp[i]);}}if(dp[i] > result) result = dp[i];}return result;}
};思路：这道题真的就是完全没有思路。
我感觉精髓就在于dp数组的定义：
dp[i]为以i为下标结尾的子序列（包括i）的最长递增子序列。有了这个定义，才能知道dp数组怎么写，如果是其它的定义应该还是挺难写的。
dp数组的递推公式：
首先要清楚子序列的含义，子序列不要求连续，只要求顺序！！如果我们要求以i为结尾的最长递增子序列，那么它可以接上任何在以它之前下标为结尾的子序列（只要nums[i]大于nums[j]）。所以我们在求dp[i]的时候要遍历在在这之前的所有dp数组的值，满足条件的时候，去取其中的最大值。
同时，因为dp数组只是以i结尾的最长子序列的长度，它不是整个数组的最长子序列的长度，所有我们还要在所有的dp数组元素中取最大值，这里使用result来保存。
dp数组初始化：按照dp数组的含义，所有的元素应该初始化为1.
遍历顺序：对应i的循环——必须正序遍历；j的循环——都可以。
2.最长连续递增序列
视频讲解：动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列_哔哩哔哩_bilibili
代码随想录
代码：
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(),1);int result = 1;// dp[i]为以i下标为结尾的最长连续递增子序列的长度for(int i = 1; i < nums.size(); i++){if(nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;if(dp[i] > result) result = dp[i];}return result;}
};思路：
这道题和上一题的区别就是，这次必须要求连续。我们只能在以前一个元素为结尾的子序列上递增。不需要那个j的循环了。其余的都一样。
dp数组的含义：以下标i为结尾（包括下标i）的最长连续递增子序列的长度
dp数组的初始化：按照含义，全部初始化为1
dp数组的递推公式：如果当前元素值大于前一个元素，就可以在前一个dp元素值上加一
dp数组的遍历顺序：正序遍历
注意：dp数组只是以下标i为结尾的最长连续递增子序列，但是题上求的是整个数组的最长连续递增子序列。所以还是要用result来记录dp数组里的最大值。
3.最长重复子数组
视频讲解：动态规划之子序列问题，想清楚DP数组的定义 | LeetCode：718.最长重复子数组_哔哩哔哩_bilibili
代码随想录
代码：
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {int result = 0;vector<vector<int>> dp(nums1.size() + 1,vector(nums2.size() + 1,0));// dp[i][j] 表示以nums1以下标i - 1为结尾，和nums2以下标j - 1为结尾的子数组的最长重复子串的长度// 其中dp[0][j]和dp[i][0]都没有实际意义，用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];}}}return result;}
};思路：
最长重复子数组——子数组其实就是连续的子序列。
dp数组的含义：
dp[i][j] 表示以nums1以下标i - 1为结尾，和nums2以下标j - 1为结尾的子数组的最长重复子串的长度；其中dp[0][j]和dp[i][0]都没有实际意义，用i-1和j-1主要是为了方便初始化。这次是二维的数组，因为要涉及到两个数组的最长重复子数组。
dp数组的递推公式：
因为是dp数组是以下标i - 1和j - 1结尾的最长重复子数组，所以我们的判断条件是num1[i - 1]和nums2[j - 1]是否相等，如果相等就在dp[i - 1][j - 1]的基础上加1。
最后也是一样，要求这些dp数组元素中的最大值。
dp数组的初始化：dp[0][j]和dp[i][0]都没有实际意义，而且为了能够推出符合实际意义的dp[1][1]应该把这些元素初始化为0
dp数组的遍历顺序：正序遍历，两次for循环可以反。