代码随想录Day 43|leetcode题目：300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

提示：DDU，供自己复习使用。欢迎大家前来讨论~

文章目录

• 动态规划Part10
• • 题目一：300.最长递增子序列
  • • 解题思路：
  • 题目二：674. 最长连续递增序列
  • • 解题思路：
  • 题目三： 718. 最长重复子数组
  • • 解题思路
    • 滚动数组
• 总结

动态规划Part10

题目一：300.最长递增子序列

300. 最长递增子序列

解题思路：

• 外层循环：遍历数组 nums 的每个元素，用索引 i 表示当前考虑的元素。

• 内层循环：对于每个索引 i，遍历从 0 到 i-1 的所有元素，用索引 j 表示这些元素。

• 子序列比较：对于内层循环中的每个索引 j，比较 nums[j]（子序列的最后一个元素）和 nums[i]（当前考虑加入的元素）。

• 子序列更新：

  • 如果 nums[i] 大于 nums[j]，则 nums[i] 可以被添加到以 nums[j] 结尾的子序列中，形成一个新的递增子序列。
  • 这意味着，对于每个 nums[i]，我们都尝试将其添加到所有可能的递增子序列中。

• 最长子序列的确定：

  • 对于每个 nums[i]，我们维护一个变量来记录以 nums[i] 为结尾的最长递增子序列的长度。
  • 这个长度是所有尝试将 nums[i] 添加到以 nums[0] 到 nums[i-1] 为结尾的递增子序列后，得到的最长子序列长度的最大值。

• 结果：算法结束时，得到的最大值即为整个数组 nums 的最长递增子序列的长度。

正解：从任意位置开始，但以nums【i】元素作为结尾的所有 递增子序列中，最长的子序列长度为 dp【i】

• dp[i] 表示的是以 nums[i] 为结尾的最长递增子序列的长度，这个子序列可以开始于数组中的任何位置。
• 动态规划数组 dp 的每个元素 dp[i] 都是独立的，它表示以 nums[i] 为结尾的最长递增子序列，而不是从 nums[0] 到 nums[i] 的连续子序列。
• 为了计算 dp[i]，我们需要检查所有先前的元素 nums[0] 到 nums[i-1]，看它们是否可以作为递增子序列的一部分，使得 nums[i] 成为这个子序列的最后一个元素。

用动规五部曲来详细分析一波：

1. dp[i]的定义

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

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

2. 状态转移方程

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

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

注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

3. dp[i]的初始化

每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.

4. 确定遍历顺序

dp[i] 是有0到i-1各个位置的最长递增子序列 推导而来，那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。 所以默认习惯 从前向后遍历。

遍历i的循环在外层，遍历j则在内层，代码如下：

for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取长的子序列
}

5. 举例推导dp数组

输入：[0,1,0,3,2]，dp数组的变化如下：

以上五部分析完毕，C++代码如下：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取长的子序列}return result;}
};

• 时间复杂度: O(n^2)
• 空间复杂度: O(n)

题目二：674. 最长连续递增序列

674. 最长连续递增序列

解题思路：

本题要求的是最长连续递增序列

动规五部曲分析如下：

  1. 确定dp数组（dp table）以及下标的含义

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

注意这里的定义，一定是以下标i为结尾，并不是说一定以下标0为起始位置。

2. 确定递推公式

   如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。

   即：dp[i] = dp[i - 1] + 1;

   在寻找数组中最长连续递增子序列时，如果 nums[i] 大于 nums[i - 1]，则以 nums[i] 为结尾的连续递增子序列长度等于以 nums[i - 1] 为结尾的连续递增子序列长度加1，这可以通过单层循环实现，而不需要两层循环来比较所有元素。

3. dp数组如何初始化

   以下标i为结尾的连续递增的子序列长度最少也应该是1，即就是nums[i]这一个元素。

   所以dp[i]应该初始1;

4. 确定遍历顺序

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

   本文在确定递推公式的时候也说明了为什么本题只需要一层for循环，代码如下：

   for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}
   }
   

5. 举例推导dp数组

   已输入nums = [1,3,5,4,7]为例，dp数组状态如下：

   

   以上分析完毕，C++代码如下：

   class Solution {
   public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);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;}
   };
   

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)

题目三： 718. 最长重复子数组

718. 最长重复子数组

解题思路

要找到两个数组中最长的重复子数组（连续子序列），步骤：

1. 两层循环：首先使用两层循环遍历两个数组，确定可能的起始位置对。
2. 单层循环或while循环：对于每一对起始位置，从这两个位置开始，逐个比较两个数组中的元素，直到遇到不匹配的元素或达到数组末尾。
3. 记录长度：在比较过程中，如果元素匹配，则更新一个计数器来记录当前匹配的子数组长度，这将是最长重复子数组的长度。

这种方法的时间复杂度较高，但对于小规模数据或简单场景下是可行的。

动态规划是解决两个字符串之间最长重复子数组问题的有效方法。

1. 确定dp数组及其下标含义：

   • dp[i][j] 表示以数组A的下标 i-1 结尾和数组B的下标 j-1 结尾的最长重复子数组的长度。
   • 注意，这里的下标是从1开始的，因为 dp[0][0] 没有实际含义。

2. 确定递推公式：

   • 如果 A[i-1] 等于 B[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1。
   • 否则，dp[i][j] = 0，因为不匹配时子数组长度重置为0。

3. dp数组如何初始化：

   • dp[i][0] 和 dp[0][j] 都初始化为0，因为它们没有实际含义，但需要这样的初始化来满足递推公式。

4. 确定遍历顺序：

   • 外层循环遍历数组A，内层循环遍历数组B。

   • 也可以反过来，这不影响算法的正确性，但会影响代码的实现细节。

   • 在遍历过程中，需要记录 dp 数组中的最大值，这个最大值就是两个数组之间最长重复子数组的长度。

代码如下：

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];}
}

5. 举例推导dp数组

拿示例1中，A: [1,2,3,2,1]，B: [3,2,1,4,7]为例，画一个dp数组的状态变化，如下：

以上五部曲分析完毕，C++代码如下：

// 版本一
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 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;}if (dp[i][j] > result) result = dp[i][j];}}return result;}
};

• 时间复杂度：O(n × m)，n 为A长度，m为B长度
• 空间复杂度：O(n × m)

滚动数组

在如下图中：

为了优化空间复杂度，可以将二维的dp数组压缩成一维，此时在遍历B数组时需要从后向前进行，以避免在更新dp值时覆盖还未使用的元素。

// 版本二
class Solution {
public:int findLength(vector<int>& A, vector<int>& B) {vector<int> dp(vector<int>(B.size() + 1, 0));int result = 0;for (int i = 1; i <= A.size(); i++) {for (int j = B.size(); j > 0; j--) {if (A[i - 1] == B[j - 1]) {dp[j] = dp[j - 1] + 1;} else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作if (dp[j] > result) result = dp[j];}}return result;}
};

• 时间复杂度：$O(n\times m)$，n 为A长度，m为B长度
• 空间复杂度：$O(m)$

---

总结

1. 状态定义：
   • 300. 最长递增子序列：定义 dp[i] 为考虑到第 i 个元素时，能形成的最长递增子序列的长度。
   • 674. 最长连续递增序列：定义 dp[i] 为以第 i 个元素结尾的最长连续递增序列的长度。
   • 718. 最长重复子数组：定义 dp[i][j] 为数组A的后 i 个元素和数组B的后 j 个元素的最长重复子数组长度。
2. 状态转移方程：
   • 300：dp[i] = max(dp[i], dp[j] + 1) 对所有 j < i，如果 nums[j] < nums[i]。
   • 674：dp[i] = dp[i-1] + 1 如果 nums[i] > nums[i-1]，否则 dp[i] = 1。
   • 718：dp[i][j] = dp[i-1][j-1] + 1 如果 A[i] == B[j]，否则 dp[i][j] = 0。
3. 初始化和遍历顺序：
   • 初始化：所有 dp 数组的初始值需要根据问题的具体要求来设定，通常是0或1。
   • 遍历顺序：根据状态转移方程的要求，确定如何遍历数组或字符串。对于 300 和 674，通常从前向后遍历；对于 718，可能需要两层嵌套循环来遍历两个数组。