别再死记 DP 了：最长递增子序列，其实是在“克制贪心”

别再死记 DP 了最长递增子序列其实是在“克制贪心”说实话我见过太多人一提到“最长递增子序列LIS”第一反应就是 “这题我背过DP 模板题。”然后写出一个 O(n²) 的解法过了面试转头就忘。但你如果只把它当模板题那你真的错过了它最有价值的部分LIS本质上是在教你——什么时候该贪什么时候该忍。今天这篇我们就把 LIS 彻底讲透而且不是那种“死板讲解”而是从思维层面让你真正理解它。一、先从一个很真实的场景说起假设你在做投资每天都有一个收益[10, 9, 2, 5, 3, 7, 101, 18]你只能选择“递增”的收益路径越投越高问最多能连续投几次这其实就是 最长递增子序列问题答案是[2, 3, 7, 101] → 长度 4二、最直觉的思路暴力 回溯但没用很多人一开始会想 枚举所有子序列筛选递增的这个思路没错但复杂度是O(2ⁿ)n100 就直接爆炸了。所以我们要更聪明一点。三、经典解法一动态规划DP这是大家最熟悉的版本。核心思想定义dp[i] 以 nums[i] 结尾的 LIS 长度状态转移dp[i] max(dp[j] 1) (j i 且 nums[j] nums[i])代码实现带详细注释deflength_of_lis_dp(nums): 动态规划解法 时间复杂度O(n^2) ifnotnums:return0# 初始化每个元素至少可以单独成为一个子序列dp[1]*len(nums)foriinrange(len(nums)):forjinrange(i):# 如果当前元素可以接在 nums[j] 后面ifnums[j]nums[i]:# 尝试更新 dp[i]dp[i]max(dp[i],dp[j]1)# 返回最大值returnmax(dp) 这个解法的问题好理解 ✅但慢 ❌O(n²)当 n 上万时基本就不行了。四、进阶解法贪心 二分核心精华接下来才是 LIS 真正“高级”的地方。一个关键问题我们是不是必须“记录完整序列”其实不用。我们只需要维护一个数组tails[i] 长度为 i1 的递增子序列的最小结尾举个例子nums [10, 9, 2, 5, 3, 7, 101, 18]过程大概是[10] [9] [2] [2, 5] [2, 3] [2, 3, 7] [2, 3, 7, 101] [2, 3, 7, 18]注意最后一步 我们把 101 替换成了 18❗ 关键洞察我们不关心序列本身只关心“未来更有潜力”的结尾。代码实现核心importbisectdeflength_of_lis(nums): 贪心 二分查找 时间复杂度O(n log n) tails[]fornuminnums:# 找到 num 在 tails 中的位置idxbisect.bisect_left(tails,num)ifidxlen(tails):# 如果 num 比所有元素都大直接追加tails.append(num)else:# 否则替换掉第一个 num 的元素# 这样可以让序列“更优”更小的结尾tails[idx]numreturnlen(tails)五、很多人卡住的点为什么可以“替换”这是 LIS 的灵魂问题。我们来讲清楚。❌ 错误直觉“替换之后序列不是变了吗”是的变了。但问题是我们要的是长度不是具体路径。✔️ 正确理解假设[2, 3, 7, 101]如果变成[2, 3, 7, 18]哪个更好 显然是 18因为18 更小更容易接后续元素一句话总结我们在牺牲“当前最优路径”换取“未来更大可能性”。六、LIS 的一个隐藏用法最长上升趋势这个算法其实在很多地方都在用 应用场景股票趋势分析用户行为增长路径排序最少修改次数信号处理举个例子最少删除元素使数组递增答案 n - LIS长度七、再进阶一点如何还原序列上面的 O(n log n) 解法只返回长度。如果你想要具体序列需要 额外记录路径前驱数组这里我给一个简化版本defreconstruct_lis(nums):importbisect tails[]prev[-1]*len(nums)indices[]fori,numinenumerate(nums):posbisect.bisect_left(tails,num)ifposlen(tails):tails.append(num)indices.append(i)else:tails[pos]num indices[pos]iifpos0:prev[i]indices[pos-1]# 回溯构造结果res[]kindices[-1]whilek0:res.append(nums[k])kprev[k]returnres[::-1]八、Echo_Wish 的一点思考很重要讲点“算法之外”的东西。我一直觉得LIS 是最像人生的一道题。为什么因为它在告诉你一件很反直觉的事 1. 不是所有“更大”的都值得保留101 比 18 大但我们选择了 18。 因为未来更重要。 2. 有时候“放弃”才是最优策略替换其实就是一种“主动放弃”。 3. 真正的高手不是一路狂飙而是“持续可增长”LIS 追求的是稳定递增而不是短期爆发九、最后一句话如果你只记住一个结论那就是LIS 的本质不是动态规划也不是二分查找而是——对未来空间的优化。写代码也是一样不是把当前写到最好而是让未来更容易扩展