题目描述
找最长的严格递增子序列的长度(元素可不相邻)。
nums = [1, 5, 2, 4, 3]
输出 = 3 （如 1,2,3 或 1,2,4）
思路解析
长度 n 的数组有 2ⁿ 个子序列，逐个检查是否递增、再比长度，指数级爆炸，n 一大就算不动。痛点在于：每检查一个新子序列都要从头看一遍，前面算过的全白算了。
换个思路：把「求全局最长」拆成「以每个数结尾的最长是多少」这种小问题，并记下来。算 dp[i] 时只问一句：前面比我小的数里，谁的 dp 最大？接在它后面 +1——小问题的答案直接查，绝不重算。
建表 · 全 1：表头是 nums 的值。每个 dp 先初始化为 1（最差也能自成一个长度为 1 的序列）。
dp[1] (值5)：5 前面有 1 比它小，接在 1 后面：dp[1] = dp[0]+1 = 2。
dp[2] (值2)：2 前面只有 1 比它小（5 不算），dp[2] = dp[0]+1 = 2。
dp[3] (值4)：4 前面有 1 和 2 比它小，挑它们里 dp 最大的（都是 2），dp[3] = 2+1 = 3。
dp[4] (值3)：3 前面比它小的有 1（dp=1）和 2（dp=2），要在所有候选里挑最大：max(1+1, 2+1) = 3。
答案 = max(dp)：注意答案是整张表的最大值（不是最后一个），这里 = 3。
DP 的本质是「最优子结构」——大问题的最优解由子问题的最优解拼成；「以 i 结尾」只是把子问题切出来的常用手法，每个 dp[i] 都是算好就记住的小答案。
参考代码（Python）
Python
1dp = [1] * len(nums)
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
- 空间复杂度：O(n) —— dp 数组
套路模板
记住骨架：dp[i] 以 i 结尾、内层回看 j、答案取 max(dp)。只要改 can_extend 这一行条件，最长数对链、俄罗斯套娃信封等一大类题都能套。
Python
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]易错点
- ❌ 返回 dp[-1] → ✅ 返回 max(dp)（最长子序列不一定以最后一个数结尾）
- ❌ 用 <= 判断 → ✅ 严格递增用 <（相等不算递增）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。