动态规划实战：子序列问题的核心模型与优化
前言：从 O(N) 到 O(N²)
和子数组（必须连续）不同，子序列允许跳跃选择。这看似简单的区别，却彻底改变了状态转移的逻辑。
核心心法：
- 状态定义：
dp[i]通常表示以i位置结尾的最长子序列长度。 - 状态转移：由于不连续，
i可以接在0到i-1之间任何一个符合条件的j后面。因此通常需要双层循环遍历。 - 高阶技巧：如果一个数定不下规律（比如等差、斐波那契），那就定两个数（
dp[i][j]表示以i和j结尾）。
最长递增子序列 (LIS)
题目描述
找到最长严格递增子序列的长度。
示例：
输入：[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();
if (n == 0) return 0;
// 初始化为 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;
}
};
