题目描述
找最长的严格递增子序列的长度(元素可不相邻)。
思路解析
长度 n 的数组有 2ⁿ 个子序列，逐个检查是否递增、再比长度，指数级爆炸，n 一大就算不动。痛点在于：每检查一个新子序列都要从头看一遍，前面算过的递增段全白算了。
换个思路：把「求全局最长」拆成「以每个数结尾的最长是多少」这种小问题，并记进 dp。为什么这么拆能省？因为算 dp[i] 时只要回看前面：哪些数比我小（能接在我前面），就在它们的 dp 里挑最大的 +1。前面每个 dp[j] 都是算好存着的，直接查、绝不重算。
建表 · 全 1：表头是 nums 的值。每个 dp 先初始化为 1——最差情况，每个数自己就是一条长度 1 的递增序列。下面从左往右逐个修正。
dp[0..2] · 前面没更小的：前三个数 10、9、2：要么前面没有数，要么前面的数都不比自己小，接不上谁，dp 全保持 1。注意数组在下降，没有递增链可拼。
dp[3] (值5) · 回看：轮到 5。回看前面：10、9 都不比 5 小，接不上；2 比 5 小，能接！dp[3] = dp[2]+1 = 2（链是 2,5）。
dp[4] (值3) · 回看：轮到 3。前面比它小的只有 2（5 不算，5 大于 3），dp[4] = dp[2]+1 = 2（链是 2,3）。
dp[5] (值7) · 回看 j=2：重点拆 7 这一格——它要回看前面每一个 j。先看 j=2（值 2）：2 小于 7，能接，候选长度 dp[2]+1 = 2。先记着这个候选。
dp[5] (值7) · 回看 j=3：继续回看 j=3（值 5）：5 小于 7，能接，候选 dp[3]+1 = 3。比刚才的 2 更长，取大，候选升到 3（链 2,5,7）。j=4（值 3）也小于 7，但 dp[4]+1=3 没更大，不变。
dp[5] (值7) · 负例 j=0：负例：回看 j=0（值 10），10 不小于 7，接在它后面就不递增了，直接跳过，不更新。j=1（值 9）同理也跳过。所有 j 看完，dp[5] 取所有候选最大 = 3。
dp[6] (值101) · 回看：101 比前面每个数都大，全都能接。回看时挑它们里 dp 最大的——是 dp[5]=3，所以 dp[6] = 3+1 = 4（链 2,5,7,101）。这就是目前最长的。
dp[7] (值18) · 回看：18 比 101 小（接不上 101），但比 7 等都大，挑 dp 最大的 dp[5]=3，dp[7] = 3+1 = 4（链 2,5,7,18）。
答案 = max(dp)：答案是整张表的最大值（不是最后一个！），dp[6]、dp[7] 都是 4，所以最长递增子序列长度 = 4。
DP 的本质是「最优子结构」——大问题的最优解由子问题的最优解拼成；「以 i 结尾」只是把子问题切出来的常用手法，每个 dp[i] 都是算好就记住的小答案。
参考代码（Python）
1dp = [1] * len(nums) # 每个数自成长度 1
2for i in range(len(nums)):
3 for j in range(i): # 回看 i 前面每个数
4 if nums[j] < nums[i]: # 严格小才能接
5 dp[i] = max(dp[i], dp[j] + 1)
6return max(dp) # 答案是整张表最大值复杂度分析
- 时间复杂度：O(n²) —— 每个 i 都要回看它前面所有 j，约 n×n/2 次
- 空间复杂度：O(n) —— 一个长度 n 的 dp 数组
套路模板
记住骨架：dp[i] 以 i 结尾、内层回看 j、答案取 max(dp)。只要改 can_extend 这一行条件，最长数对链、俄罗斯套娃信封等一大类题都能套。
1# 凡是「最长 / 最优子序列」都能套这个骨架
2dp = [1] * n # dp[i]: 以 i 结尾的最优解
3for i in range(n):
4 for j in range(i): # 回看前面每个 j
5 if can_extend(j, i): # 满足转移条件才接
6 dp[i] = max(dp[i], dp[j] + 1)
7return max(dp) # 答案在整张表里找，不是 dp[-1]易错点
- 错误写法：return dp[-1] → 正确写法：return max(dp)（最长链不一定以最后一个数结尾。本例 dp[-1]=dp[7]=4 碰巧对，但若把 18 换成小数 dp[-1] 就偏小，必须取整张表 max）
- 错误写法：if nums[j] <= nums[i]（用小于等于） → 正确写法：严格用 nums[j] < nums[i]（题目要严格递增，相等不算递增；用 <= 会把 [2,2] 也当成长度 2，答案偏大）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。