代码随想录算法训练营19期第52天

300.最长递增子序列 

视频讲解：动态规划之子序列问题，元素不连续！| LeetCode：300.最长递增子序列_哔哩哔哩_bilibili

代码随想录

初步思路：动态规划。

总结：

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

用时：30分钟

 674. 最长连续递增序列 

视频讲解：动态规划之子序列问题，重点在于连续！| LeetCode：674.最长连续递增序列_哔哩哔哩_bilibili

代码随想录  

初步思路：动态规划。

总结：

dp[i]：以下标i为结尾的连续递增的子序列长度为dp[i]。

if (nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;

用时：30分钟

 718. 最长重复子数组 

视频讲解：动态规划之子序列问题，想清楚DP数组的定义 | LeetCode：718.最长重复子数组_哔哩哔哩_bilibili

代码随想录

初步思路：动态规划。

总结：

dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]

if (A[i - 1] == B[j - 1])  dp[i][j] = dp[i - 1][j - 1] + 1;

也可以简化为1D滚动数组：此时遍历B数组的时候，就要从后向前遍历，避免重复覆盖。

用时：45分钟