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