leetcode300. 最长递增子序列,动态规划附状态转移方程

leetcode300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

子序列与子串的区别

子序列（Subsequence）

• 定义：一个给定序列的子序列是从原序列中在不改变序列顺序的情况下删除某些元素（也可以不删除任何元素）而形成的序列。
• 特点：
  • 不需要连续。
  • 保持元素的原有顺序。
• 示例：对于序列 A = [5, 1, 22, 25, 6, -1, 8, 10]，[5, 22, 25] 和 [1, 6, -1] 都是它的子序列。

子串（Substring）

• 定义：子串是指从原字符串中连续取出的一部分。
• 特点：
  • 必须连续。
  • 保持元素的原有顺序。
• 示例：对于字符串 S = "abcdefg"，"abc" 和 "def" 都是它的子串。

总结

• 主要区别：子序列不要求连续，而子串必须是连续的。

最长递增子序列问题

题目描述

给定一个整数数组，找到最长的递增子序列的长度。

题目分析

这是一个经典的动态规划问题。我们可以通过计算以每个元素为结尾的最长递增子序列的长度来最终得到整个数组的最大递增子序列长度。

算法

状态转移方程

• 定义：dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。
• 转移方程：dp[i] = max(dp[i], dp[j] + 1)，其中 0 <= j < i 且 nums[i] > nums[j]。
• 解释：
  • 如果 nums[i] 大于 nums[j]，那么 nums[i] 可以加到以 nums[j] 结尾的递增子序列的末尾，形成一个新的更长递增子序列。
  • 因此，我们需要更新以 nums[i] 结尾的最长递增子序列的长度。
  • max(dp[i], dp[j] + 1) 确保了对于每个 nums[i]，我们选择一个最优的 dp[j] 来形成新的递增子序列。

初始化

• dp[i] = 1，因为任何单个元素自身都是一个递增子序列。

遍历进行状态转移

• 遍历数组，对于每个元素 nums[i]，再遍历其之前的所有元素 nums[j]，如果 nums[i] > nums[j]，则更新 dp[i]。

返回结果

• 返回 dp 数组中的最大值，即为最长递增子序列的长度。

算法流程

代码实现

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

打表过程

最终结果

• 最长递增子序列长度为 4，对应于 dp[7]。

算法分析

• 时间复杂度：O(n^2)，因为我们需要遍历数组中的每个元素，对于每个元素，我们又需要遍历其之前的所有元素。
• 空间复杂度：O(n)，用于存储 DP 数组。

易错点

• 注意在遍历时正确应用状态转移方程。
• 确保在更新 dp[i] 时考虑所有可能的 dp[j]。

相似题目

题目	链接
最长连续递增序列	LeetCode 674
俄罗斯套娃信封问题	LeetCode 354
最长公共子序列	LeetCode 1143