300.最长递增子序列

力扣题目链接/文章讲解

视频讲解

1、确定 dp 数组下标及值含义

本题中，正确定义dp数组的含义十分重要

dp[i]：下标 i 表示以 nums[i] 结尾的最长递增子序列，dp[i] 的值表示该子序列长度的

2、确定递推公式

要求 dp[i]，需要考虑以 nums[i] 结尾的最长递增子序列，注意该子序列一定包含 nums[i] 了。

我们可以按照下述方法构建所有以 nums[i] 结尾的递增子序列，再在里面找最长的

分别考虑以 nums[0]、nums[1]、nums[2]、……、nums[i - 1] 为结尾的最长递增子序列，如果 nums[i] 能够和上述递增子序列构成更长的递增子序列，需要 nums[i] 大于上述递增子序列中的最后一个元素。又因为求的是最长递增子序列，即

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

3、初始化 dp 数组

每一个 i，对应的 dp[i]（即最长递增子序列）起始大小至少都是 1，元素本身至少能构成一个长度为 1 的递增子序列

4、确定遍历顺序

根据递推公式，dp[i] 依赖于 dp[i - 1]、dp[i-2]、……、 dp[0]，因此应该从左往右遍历，保证更新 dp[i] 时，被依赖的 dp 值是已被更新的正确数值

5、打印 dp 数组验证

代码如下

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1); // 全部初始化为1for (int i = 1; i < nums.size(); ++i) { // 从左向右遍历，i从1开始即可，因为dp[0]肯定为1for (int j = 0; j <= i - 1; ++j) {  // 确定dp[i]本身内层需要一个for循环，考虑所有以nums[j]为结尾的递增子序列的最大值if (nums[i] > nums[j])    // 如果nums[i]能够和递增子序列构成更长的递增子序列dp[i] = max(dp[i], dp[j] + 1);}}return *max_element(dp.begin(), dp.end());  // 注意最后的结果。最长递增子序列不一定是以dp[nums.size() - 1]结尾的}
};

674.最长连续递增序列

力扣题目链接/文章讲解

视频讲解

1、确定 dp 数组下标及值含义

本题中，正确定义dp数组的含义十分重要

dp[i]：下标 i 表示以 nums[i] 结尾的最长连续递增序列，dp[i] 的值表示该连续序列长度的

注意该连续递增序列一定包含 nums[i] ！！！

2、确定递推公式

要求 dp[i]，需要考虑以 nums[i] 结尾的最长连续递增序列

因为“连续”，序列又要以 nums[i] 结尾

故

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

这里就体现出和上一题的区别了

因为本题要求连续递增序列，所以就只要比较 nums[i] 与 nums[i - 1]，而不用去比较 nums[j] 与nums[i]（j 是在 0 到 i 之间遍历）

既然不用 j 了，那么也不用两层 for 循环，本题一层 for 循环遍历 dp 数组就行

3、dp 数组初始化

每一个 i，对应的 dp[i]（即最长连续递增序列）起始大小至少都是 1，元素本身至少能构成一个长度为 1 的连续递增序列

4、确定遍历顺序

从递推公式上可以看出， dp[i] 依赖 dp[i - 1]，所以一定是从前向后遍历

5、打印 dp 数组验证

代码如下

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1); // 初始化为1，表示以nums[i]结尾的最长连续递增序列的长度至少为1for (int i = 1; i < dp.size(); ++i) {   // 从dp[1]开始填充即可if (nums[i] > nums[i - 1])dp[i] = dp[i - 1] + 1;  // 注意“连续”条件elsedp[i] = 1;}return *max_element(dp.begin(), dp.end());  // 最长连续递增序列不一定是以dp[nums.size()-1]结尾的}
};

718.最长重复子数组

力扣题目链接/文章讲解

视频讲解

本题最大的难点还是定义 dp 数组

需要用二维数组记录两个字符串的所有比较情况

1、确定 dp 数组下标及值的含义

dp[i][j]：nums1 中以下标 i 为结尾的某个子数组，和 nums2 中以下标 j 为结尾的某个子数组是最长重复子数组，值表示重复子数组长度为 dp[i][j]

注意两重复子数组一定是以 nums1[i] 和 nums2[j] 结尾的

2、确定递推公式

要推出 dp[i][j]，即需要看看 nums1[i] 和 nums2[j] 是否相等

如果不相等，则以 nums1[i] 结尾的 nums1 的子数组与以 nums2[j] 结尾的 nums2 的子数组必不可能为重复子数组，即 dp[i][j] = 0

如果相等，则 dp[i][j] 的值应该为 dp[i - 1][j - 1] + 1

即

if (nums1[i] != nums2[j])dp[i][j] = 0;
elsedp[i][j] = dp[i - 1][j - 1] + 1;

3、dp 数组初始化

根据递推公式，需要初始化第一行和第一列，即需要初始化 dp[0][j] 和 dp[i][0]

dp[0][j]：nums1 中以下标 0 为结尾的某个子数组，和 nums2 中以下标 j 为结尾的某个子数组是最长重复子数组，值表示重复子数组长度

for (int j = 0; j < nums2.size(); ++j)
{if (nums2[j] == nums1[0])dp[0][j] = 1;elsedp[0][j] = 0;
}

dp[i][0]：nums1 中以下标 i 为结尾的某个子数组，和 nums2 中以下标 0 为结尾的某个子数组是最长重复子数组，值表示重复子数组长度

for (int i = 0; i < nums1.size(); ++i)
{if (nums1[i] == nums2[0])dp[i][0] = 1;elsedp[i][0] = 0;
}

4、确定遍历顺序

根据递推公式，为了保证更新每一项所依赖的 dp 值已经更新，可以一层一层从左往右遍历更新

5、打印 dp 数组验证

代码如下

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int> > dp(nums1.size(), vector<int>(nums2.size()));for (int j = 0; j < nums2.size(); ++j)    // 初始化第一行{if (nums2[j] == nums1[0])dp[0][j] = 1;elsedp[0][j] = 0;}for (int i = 0; i < nums1.size(); ++i)    // 初始化第一列{if (nums1[i] == nums2[0])dp[i][0] = 1;elsedp[i][0] = 0;}for (int i = 1; i < nums1.size(); ++i)for (int j = 1; j < nums2.size(); ++j) {    // 从上往下从左往右if (nums1[i] == nums2[j])dp[i][j] = dp[i - 1][j - 1] + 1;elsedp[i][j] = 0;} int result = -1;for (auto & line : dp)for (auto i : line)result = max(i, result);    // 结果为dp数组中的最大值return result;}
};

注意结果应该为 dp[i][j] 中的最大值。因为

dp[i][j]：nums1 中以下标 i 为结尾的某个子数组，和 nums2 中以下标 j 为结尾的某个子数组是最长重复子数组，值表示重复子数组长度为 dp[i][j]

而最终最长的重复子数组的末尾可能是对应任意的 nums1 和 nums2 中的下标