动态规划求最长递增子序列的核心是定义dp[i]为以nums[i]结尾的最长严格递增子序列长度，状态转移需遍历i前所有j满足nums[j]
动态规划是解决最长递增子序列（LIS）最直观且通用的方法，核心在于合理定义状态、写出转移关系，并高效计算。
明确 dp[i] 的含义
定义 dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度。这个定义很关键——它把“全局最长”拆解为“每个位置结尾的局部最优”，避免了子序列不连续带来的复杂性。
- 例如 nums = [10,9,2,5,3,7]，dp[3] 对应数字 5，表示所有以 5 结尾的递增子序列中最长的那个长度（这里是 [2,5] → 长度为 2）
- 每个 dp[i] 至少为 1，因为单个元素本身构成长度为 1 的递增子序列
写出状态转移方程
要算 dp[i]，需检查 i 之前所有位置 j（0 ≤ j
- 转移式：dp[i] = max(dp[i], dp[j] + 1)，对所有满足 nums[j]
- 初始时 dp[i] = 1，再不断用合法的 dp[j] + 1 更新它
- 注意不是“选一个 j”，而是遍历所有 j 取最大值
按顺序填表并取结果
由于 dp[i] 依赖所有 dp[j]（j
- 外层循环 i 从 1 到 n−1（i=0 时 dp[0]=1 已确定）
- 内层循环 j 从 0 到 i−1，判断能否转移
- 过程中持续记录最大值，最终答案就是 dp 数组里的最大值，而非 dp[n−1]
时间与空间开销
标准 DP 解法时间复杂度为 O(n²)，空间为 O(n)。对长度 ≤ 2500 的输入完全可行；若需进一步优化至 O(n log n)，可用贪心 + 二分维护“各长度下末尾最小值”的数组，但那是进阶策略，基础 DP 已覆盖绝大多数实际需求。
