LIS 模型及其衍生
一、前言：从 O(N) 到 O(N²)
开篇：和子数组（必须连续）不同，子序列可以跳着选。
核心心法：状态定义：
dp[i]表示以i位置结尾的最长子序列…状态转移：因为不连续，所以i可以接在0到i-1任何一个符合条件的j后面。因此通常需要一个双层循环。高阶技巧：如果一个数定不下规律（比如等差、斐波那契），那就定两个数（dp[i][j]表示以i和j结尾）。
二、最长递增子序列 (Medium)
2.1 题目描述
题目链接：300. 最长递增子序列
描述：找到最长严格递增子序列的长度。
示例：输入
[10,9,2,5,3,7,101,18]，输出4([2,3,7,101])
2.2 核心思路：LIS 模型
- 状态：
dp[i]表示以nums[i]结尾的最长递增子序列长度。 - 转移：站在
i位置，往回看所有j(0 <= j < i)。如果nums[j] < nums[i]，说明能接在j后面。选一个最长的dp[j]接上去。dp[i] = max(dp[j] + 1)。
2.3 代码实现
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
// 初始化为 1，因为每个元素自己就是一个长度为 1 的子序列
vector<int> dp(n, 1);
int ret = ;
( i = ; i < n; i++) {
( j = ; j < i; j++) {
(nums[j] < nums[i]) {
dp[i] = (dp[i], dp[j] + );
}
}
ret = (ret, dp[i]);
}
ret;
}
};
