第9章｜动态规划
Unit 10 · LeetCode #300 最长递增子序列
不是“前缀里最好”，
而是“必须在这里结束”。
最大子数组和已经展示过局部状态与全局答案的分离。本单元把这种思想迁移到非连续选择：dp[i] 不表示前缀整体最优，而表示必须以 nums[i] 结尾的最长严格递增子序列长度。
已恢复上次学习位置阶段、动画、答题、代码槽位和迁移进度均已恢复。
知识桥梁｜Unit 09 → Unit 10
Unit 09：坐标决定前驱
网格中的当前格只能从上方或左方到达，前驱结构由空间位置固定。
固定前驱 → 扫描全部左侧
Unit 10：数值决定前驱
索引 j 只有同时满足 j < i 与 nums[j] < nums[i]，才可连接到当前结尾。
本单元贯穿问题当前状态必须以哪个元素结尾？哪些左侧位置可以成为合法前驱？最终答案为什么可能不在最后一个状态？
LeetCode #300 原题题面转述、示例、约束与提交签名
题目要求
给定整数数组 nums，返回其中最长严格递增子序列的长度。子序列可以删除若干元素，但保留下来的元素必须维持原数组中的相对顺序；它不要求连续。
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
pass
约束
1 ≤ nums.length ≤ 2500-10⁴ ≤ nums[i] ≤ 10⁴- 严格递增使用
<，相等元素不能连接。
示例
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
一种最长递增子序列：[2,3,7,101]
输出：4
一种最长递增子序列：[2,3,7,101]
输入：nums = [0,1,0,3,2,3]
输出：4
输出：4
输入：nums = [7,7,7,7,7,7,7]
输出：1
输出：1
主方法
本页主动画采用 O(n²) 动态规划，以完整呈现状态语义和前驱关系；进阶的贪心＋二分可达到 O(n log n)。
| 方法 | 时间 | 空间 | 本章用途 |
|---|---|---|---|
| 枚举全部子序列 | O(2ⁿ) | O(n) | 看见组合爆炸 |
| 以结尾位置为状态的 DP | O(n²) | O(n) | 主教学方法，可解释前驱与方案数量 |
| 贪心＋二分 tails | O(n log n) | O(n) | 进阶优化；tails 不一定是一条真实 LIS |
六段主流程
本环节已完成
请停留观察当前状态，确认你能解释高亮状态的含义。
1 / 6