第一次把“最长递增子序列的个数”这七个字放进编辑器的时候我以为只是给经典的 LIS 问题加一个计数器。毕竟长度能求数量不就是多维护一个变量的事吗真正写完并跑完几个用例我才发现这道题想让你掌握的是“最优解有多个分支时如何不重不漏地计数”。它几乎是动态规划计数思想的缩影。这篇文章把我的完整思考过程写下来从朴素 O(n²) 的 DP 写法到树状数组 O(n log n) 优化再到实际写代码时容易踩的坑。如果你正在刷动态规划、或者准备算法面试这篇应该能帮你把这个模型彻底吃透。1. “最长递增子序列的个数”和经典 LIS 差在哪1.1 先把题目定义讲清楚给定一个整数数组 nums返回其中最长递增子序列的个数。子序列不要求连续但必须保持原数组相对顺序并且严格递增。注意“严格”两个字很关键相等元素不能接在后面。举个例子[1, 3, 5, 4, 7]的最长递增子序列长度是 4但满足这个长度的子序列有几个有两个[1,3,5,7]和[1,3,4,7]。所以题目要返回的是 2而不是 1。如果你只做过最长递增子序列长度的题你可能觉得把每个位置的 dp 值求出来最后统计最大值的个数就行了。但问题是dp 数组只记录长度不记录方案数。你在转移时必须额外维护“以当前位置结尾的最长递增子序列有多少条”。这就像你只知道到达终点的最短距离却不知道有多少条不同路线必须把路线数量也一起算出来。1.2 这个变体难在哪经典 LIS 的转移方程核心是取最大值对于每个 i遍历所有 j i只要nums[j] nums[i]就尝试用dp[j]1更新dp[i]。最大值的转移天然是唯一确定性的。可一旦要计数同一个长度可能由多个前驱位置贡献也可能同一个前驱位置内部还有多条不同子序列这些分支必须全部加起来。更麻烦的是累加时不能重复。比如[1, 2, 2, 3]以 3 结尾的最长递增子序列长度是 3但个数是 2[1, 第一个2, 3]和[1, 第二个2, 3]。两个 2 虽然值相同但下标不同必须算作两条不同子序列。如果你下意识用“去重”的思路把相同值的方案合并答案就错了。所以这个题本质上考的是在动态规划转移中如何处理“并列最优”的合并与去重。1.3 用一个小例子建立直觉手推[1, 3, 5, 4, 7]时我习惯把每个位置的结果写成一棵小树以 1 结尾长度 1方案数 1。以 3 结尾可以从 1 接过来长度 2方案数 1。以 5 结尾可以从 3 接过来长度 3方案数 1。以 4 结尾虽然也能从 1 接得到[1,4]长度 2但更优的是从 3 接长度 3方案数 1。以 7 结尾可以从 5 接也可以从 4 接两种都能构成长度 4所以方案数 2。这里的关键是末尾位置 7 的两个前驱分别指向不同的中等值而这两个中等值各自又只有一条最优路径于是最终方案数就是 112。一旦理解了“每个位置只记录自己的最优长度和该长度对应的方案数”后面的转移规则就顺理成章了。2. 朴素动态规划长度和计数必须同步转移2.1 状态定义dp 和 cnt 是搭档定义两个数组dp[i]以nums[i]结尾的最长递增子序列长度。cnt[i]以nums[i]结尾的、长度恰好等于dp[i]的递增子序列个数。注意cnt[i]不统计所有以nums[i]结尾的子序列只统计“最长长度”的那些。为什么可以这样因为任意一条全局最长递增子序列如果它不以nums[i]结尾那它和cnt[i]无关如果它确实以nums[i]结尾那它的长度一定等于以nums[i]结尾的最长长度。所以我们把短方案丢掉不会影响最终答案。初始化时每个位置的dp[i] 1表示单个元素本身可以组成长度 1 的递增子序列同时cnt[i] 1因为这种子序列只有一条。2.2 转移规则大于就替换相等就累加从小到大遍历 i对于每个 i再枚举所有 j i。当nums[j] nums[i]时说明nums[i]可以接在以nums[j]结尾的递增子序列后面。这时候分三种情况如果dp[j] 1 dp[i]说明发现了一条更长的路线更新dp[i] dp[j] 1并且cnt[i] cnt[j]。如果dp[j] 1 dp[i]说明又找到了一条和当前最优长度相同的路线执行cnt[i] cnt[j]。如果dp[j] 1 dp[i]说明这条路线不够长忽略。这个规则的直觉是你先找到最长长度把方案数重置为来自该前驱的方案数再遇到同样长度的路线时把方案数累加进去。2.3 手算一个完整例子我用[1, 2, 2, 3]演示一遍这个例子最能暴露问题。i0值 1dp[0]1, cnt[0]1。i1值 2前面只有 012dp[1]从 1 变成 2cnt[1]cnt[0]1。i2值 2前面 j0 的12dp[2]更新为 2cnt[2]1但 j1 的值也是 2不满足严格递增所以不能用。注意这里不能把两个相同值的 2 接起来。i3值 3先看 j013dp[0]12小于当前dp[3]1更新dp[3]2, cnt[3]1。接着 j123dp[1]13大于当前 2更新dp[3]3, cnt[3]cnt[1]1。接着 j223dp[2]13等于当前最优长度 3执行cnt[3]cnt[2]即cnt[3]2。最终全局最大长度max(dp)3把所有dp3的cnt相加得到答案 2。这 2 条分别对应两个不同下标的 2 作为倒数第二个元素虽然数值一样但确实是两条不同的子序列。2.4 代码实现与复杂度def find_number_of_lis(nums): n len(nums) if n 0: return 0 dp [1] * n cnt [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: if dp[j] 1 dp[i]: dp[i] dp[j] 1 cnt[i] cnt[j] elif dp[j] 1 dp[i]: cnt[i] cnt[j] max_len max(dp) ans 0 for i in range(n): if dp[i] max_len: ans cnt[i] return ans时间复杂度 O(n²)空间复杂度 O(n)。当数组长度在千级到两三千时这个写法足够用。但如果你碰到十万级的数据就必须往下看树状数组的优化。3. 最容易改错的三个细节初始化、重复计数和边界用例3.1 初始化不是全 1 就万事大吉很多人的第一版代码会把cnt初始化为全 1这是对的。但有些人会先给dp全 0然后在转移时用cnt[i] cnt[j]赋值结果漏掉了长度为 1 的基础方案。其实有一个更隐蔽的问题如果dp[i]初始为 1那么在转移时遇到dp[j]1也等于 1 的情况根本不会发生因为dp[j]至少是 1dp[j]1至少是 2。所以初始化为 1 是合理的。真正容易错的是最后收集答案。很多人拿到cnt数组后直接max(cnt)觉得“最长长度对应的方案数”就是答案。但最长长度可能出现在多个不同结尾位置每个位置都贡献一部分方案必须把所有dp[i] max_len的cnt[i]全部加起来。比如[2, 2, 2]每个位置的最长长度都是 1每个cnt都是 1答案不是 1 而是 3。3.2 为什么这样累加不会重复这一步是理解全题的关键。有人会问如果两个不同的前驱 j 最终生成了同一条子序列怎么办不可能。原因很简单一条以nums[i]结尾的子序列它的倒数第二个元素下标必然是某个具体的 j。如果 j 不同就算nums[j]的值相同整条子序列的下标序列也不同所以它们一定是不同子序列。比如[1, 2, 2, 3]里的两条最长序列倒数第二个下标分别是 1 和 2这就是两个不同的序列。那么同一个 j 内部会不会漏算不会。cnt[j]已经统计了所有以 j 结尾、长度等于dp[j]的最优子序列。对每一条在后面接上nums[i]都得到一条不同的新序列。这些新序列之间前缀不同当然不会互相重复。所以累加是安全的。3.3 数组长度为 1 和所有元素相等的极端用例写这个题边界用例必须自己先跑一遍。nums [5]返回 1。nums [5, 5, 5]因为严格递增任何相同值都不能相接所以每个位置都是长度 1 的独立子序列返回 3。nums [5, 4, 3, 2, 1]严格递减同理每个位置都只能作为单元素子序列返回数组长度 n。这些边界用例如果跑错通常说明你的转移条件写成了或者最后统计时把相同值合并了。请记住递增子序列的定义是严格递增等于号是大忌。3.4 计数溢出问题方案数可能非常大尤其是当数组故意构造出很多并列分支时数量会指数级增长。C 里如果用int存cnt很容易溢出。换long long会更稳如果题目要求取模比如和 1e97 取模那就在累加和赋值时都取模。Python 没有溢出问题但在很多实际工程场景中还是要注意数值上限。遇到这种计数题我习惯先用 64 位整数再根据题目要求决定是否取模。4. 树状数组优化到 O(n log n)值域上存“长度计数”4.1 从 O(n²) 到 O(n log n) 的优化思路朴素 DP 慢在哪儿慢在每次处理 i 时都要把所有 j i 扫一遍。但仔细看转移过程我们要找的是所有满足nums[j] nums[i]的 j 中最大的dp[j]是谁以及在这些取到最大dp[j]的 j 身上cnt[j]的总和是多少。换句话说我们需要的是一次“值域上的前缀查询”在数值小于nums[i]的所有已处理元素里查它们的最长长度和对应方案数。如果我们能按数值大小建一个数据结构把已经扫描过的位置按nums[j]的值存进去每次只需要查询前缀区间的聚合信息就能把内层循环的 O(n) 降成 O(log n)。这就是树状数组的切入点。4.2 离散化把数值压缩成有序下标nums里的数值范围可能很大甚至可能有负数直接下标建不了树。所以第一步先排序去重把值映射成 1 到 m 的秩。例如nums [10, 3, 7, 3]去重排序后得到[3, 7, 10]映射关系是3 - 1, 7 - 2, 10 - 3。树状数组长度 m 就是不同数值的个数空间 O(n)。这里有个很关键的细节我们要查的是“严格小于nums[i]的前缀”所以查询的下标是rank(nums[i]) - 1而不是rank(nums[i])。如果查询时把等于当前值的部分也包含进去就会把相同值的方案接在后面变成非严格递增答案立刻错误。我一开始就是在这里栽的。4.3 树状数组节点里存什么普通树状数组每个节点存一个数值的某种聚合这里每个节点要存两个东西len和cnt含义是“该节点管辖的值域范围内以这些值作为结尾时能达到的最长递增子序列长度以及这个长度对应的方案总数”。为什么可以只存最长长度而不保留短长度因为同一个数值可能出现在多个位置这些位置的 dp 值不一定相同。但后续元素想要接在这个值后面时它得到的长度一定等于“以该值结尾的最长长度加 1”。短方案接上去得到的长度永远不可能超过最优方案接上去的结果。所以短方案在这个值上是安全的可以丢掉。不过要注意同一个值如果多个不同位置都达到了当前最长长度它们的方案数必须累加。比如[1, 2, 2, 3]值 2 出现在两个位置且两个位置的 dp 都是 2方案数都是 1。那么值 2 这个桶里最终存的应该是len2, cnt2。这样后续元素 3 查询到值 2 时才能得到 2 条不同的路径。4.4 前缀查询与点更新的实现细节代码里需要实现一个合并函数处理两个二元组(len1, cnt1)和(len2, cnt2)如果len1 len2取第一个。如果len2 len1取第二个。如果长度相等且长度不为 0计数相加。如果两个长度都是 0说明该区间还没有有效状态计数保持 0。树状数组的前缀查询会访问多个互不相交的区间节点把它们的二元组按上述规则合并点更新则沿着树往上走把当前计算出的(cur_len, cur_cnt)合并到经过的每个节点中。from bisect import bisect_left def find_number_of_lis(nums): if not nums: return 0 vals sorted(set(nums)) m len(vals) bit_len [0] * (m 1) bit_cnt [0] * (m 1) def query(i): best_len 0 best_cnt 0 while i 0: if bit_len[i] best_len: best_len bit_len[i] best_cnt bit_cnt[i] elif bit_len[i] best_len and bit_len[i] ! 0: best_cnt bit_cnt[i] i - i -i return best_len, best_cnt def update(i, length, cnt): while i m: if length bit_len[i]: bit_len[i] length bit_cnt[i] cnt elif length bit_len[i] and length ! 0: bit_cnt[i] cnt i i -i for num in nums: idx bisect_left(vals, num) 1 pre_len, pre_cnt query(idx - 1) if pre_len 0: cur_len, cur_cnt 1, 1 else: cur_len, cur_cnt pre_len 1, pre_cnt update(idx, cur_len, cur_cnt) _, ans query(m) return ans我用[1, 2, 2, 3]验证一下这个流程处理第一个 2 时查询小于 2 的前缀得到值 1 的(len1, cnt1)于是算出(len2, cnt1)更新到值 2。处理第二个 2 时同样查询小于 2 的前缀仍然得到(1, 1)算出(2, 1)更新时发现值 2 已经有(2, 1)长度相等所以累加为(2, 2)。处理 3 时查询小于 3 的前缀合并值 1 和值 2 的信息得到(2, 2)于是算出(3, 2)。最终答案 2。这个例子里同一数值的多个位置通过点更新累加计数完美处理了重复值的情况。4.5 完整代码和复杂度分析上面的代码就是完整实现。时间上每个元素做一次查询和一次更新都是 O(log n)所以总复杂度 O(n log n)。空间上树状数组和离散化数组都是 O(n)。相比朴素 DP树状数组方案不只快了一个量级更重要的是它把“位置维度”的枚举转化成了“值域维度”的聚合这种思想在很多类似计数题里都能复用动态规划状态若能写成“前缀最优 计数”往往就能用线段树或树状数组优化。5. 面试追问与变体为什么贪心二分、如何输出路径5.1 为什么贪心二分算法不适合直接计数很多熟悉 LIS 的人第一反应是用经典贪心二分维护tails数组每个长度存一个最小末尾值。这个算法求长度很快但直接用它求个数会遇到一个问题它为了追求 O(n log n)在每个长度上只保留“最小的那个末尾值”丢掉了所有并列末尾值以及它们对应的路径数量。比如[1, 3, 5, 4, 7]在求长度时长度 3 的最小末尾值会保留 4而 5 被丢掉了。但对计数来说5 和 4 都能接到 7 后面构成长度 4这两个都必须保留。所以贪心二分的状态压缩方向是“记录最小末尾值加速比较”不是“记录所有并列方案”直接套上去会严重漏算。如果面试官追问“为什么不用贪心二分”你可以回答贪心二分适合单值比较不适合多方案累积计数需要的是“前缀最大值的数量”树状数组或线段树可以天然维护这种聚合关系。5.2 如果需要输出所有最长递增子序列怎么办有时候题目会升级成“输出所有最长递增子序列”。这时候计数 DP 还不够因为你不仅要数出有几条还要把每条具体序列列出来。一个可行的做法是先用朴素 DP 求出每个位置的dp[i]然后从所有dp[i] max_len的位置触发做 DFS 反向回溯。回溯的时候对于当前位置 i枚举 j i如果满足nums[j] nums[i]且dp[j] 1 dp[i]那么 j 就是一个合法的前驱继续向前递归。注意如果方案数是指数级输出所有序列本身也是指数级任何算法都无法避免。所以这种问题通常只适合小数据量或者题目只要求“方案数”而不是“具体方案”。计数是轻量级的枚举是重量级的两者不能混为一谈。5.3 相关变体非严格递增、最长递减、二维 LIS掌握这个模型后几个变体其实都可以举一反三如果要求非严格递增也就是相等元素可以接在后面转移条件从nums[j] nums[i]改成nums[j] nums[i]树状数组查询时查rank(nums[i])而不是rank(nums[i]) - 1。但要注意此时相同值之间也可以接查询和更新的顺序要小心避免一个元素“自己接自己”。因为我们是先查询再更新所以不会出现同一位置自接的问题。如果要求最长递减子序列的个数可以反转数组然后对反转后的数组求最长递增子序列个数或者把所有数取负再套用递增模板。二维 LIS比如信封嵌套问题通常先按一个维度排序再对另一个维度求 LIS。如果两个维度的值有重复要先处理排序时的相等情况否则会把不该嵌套的信封接在一起。计数逻辑依然沿用“长度 方案数”的思路。这些变体在工程里也有实际对应场景比如事件序列中寻找最长趋势性片段并统计不同趋势片段的个数。理解了这个题你再遇到“最长公共子序列计数”“最长连续子序列计数”这类问题会发现底层逻辑都是相通的。最后说一点个人体会。我第一次独立写这个题用了将近二十分钟才把计数细节理清最大的收获不是记住转移方程而是明白了“最大值唯一时计数很简单最大值并列时计数才是真正的考点”。后来我把树状数组方案也补上对“可合并状态”的理解又上了一个台阶。再遇到类似题目我会先想朴素 DP 状态能不能多带一个cnt再想这个cnt能否用前缀数据结构维护。这套打法在不少计数类动态规划题里都很好用希望也能给你一点启发。 
长河君 · 2026/10/10 4:14:35 · 阅读 1.2k 最长递增子序列个数：从动态规划到树状数组的优化全解析
第一次把“最长递增子序列的个数”这七个字放进编辑器的时候我以为只是给经典的 LIS 问题加一个计数器。毕竟长度能求数量不就是多维护一个变量的事吗真正写完并跑完几个用例我才发现这道题想让你掌握的是“最优解有多个分支时如何不重不漏地计数”。它几乎是动态规划计数思想的缩影。这篇文章把我的完整思考过程写下来从朴素 O(n²) 的 DP 写法到树状数组 O(n log n) 优化再到实际写代码时容易踩的坑。如果你正在刷动态规划、或者准备算法面试这篇应该能帮你把这个模型彻底吃透。1. “最长递增子序列的个数”和经典 LIS 差在哪1.1 先把题目定义讲清楚给定一个整数数组 nums返回其中最长递增子序列的个数。子序列不要求连续但必须保持原数组相对顺序并且严格递增。注意“严格”两个字很关键相等元素不能接在后面。举个例子[1, 3, 5, 4, 7]的最长递增子序列长度是 4但满足这个长度的子序列有几个有两个[1,3,5,7]和[1,3,4,7]。所以题目要返回的是 2而不是 1。如果你只做过最长递增子序列长度的题你可能觉得把每个位置的 dp 值求出来最后统计最大值的个数就行了。但问题是dp 数组只记录长度不记录方案数。你在转移时必须额外维护“以当前位置结尾的最长递增子序列有多少条”。这就像你只知道到达终点的最短距离却不知道有多少条不同路线必须把路线数量也一起算出来。1.2 这个变体难在哪经典 LIS 的转移方程核心是取最大值对于每个 i遍历所有 j i只要nums[j] nums[i]就尝试用dp[j]1更新dp[i]。最大值的转移天然是唯一确定性的。可一旦要计数同一个长度可能由多个前驱位置贡献也可能同一个前驱位置内部还有多条不同子序列这些分支必须全部加起来。更麻烦的是累加时不能重复。比如[1, 2, 2, 3]以 3 结尾的最长递增子序列长度是 3但个数是 2[1, 第一个2, 3]和[1, 第二个2, 3]。两个 2 虽然值相同但下标不同必须算作两条不同子序列。如果你下意识用“去重”的思路把相同值的方案合并答案就错了。所以这个题本质上考的是在动态规划转移中如何处理“并列最优”的合并与去重。1.3 用一个小例子建立直觉手推[1, 3, 5, 4, 7]时我习惯把每个位置的结果写成一棵小树以 1 结尾长度 1方案数 1。以 3 结尾可以从 1 接过来长度 2方案数 1。以 5 结尾可以从 3 接过来长度 3方案数 1。以 4 结尾虽然也能从 1 接得到[1,4]长度 2但更优的是从 3 接长度 3方案数 1。以 7 结尾可以从 5 接也可以从 4 接两种都能构成长度 4所以方案数 2。这里的关键是末尾位置 7 的两个前驱分别指向不同的中等值而这两个中等值各自又只有一条最优路径于是最终方案数就是 112。一旦理解了“每个位置只记录自己的最优长度和该长度对应的方案数”后面的转移规则就顺理成章了。2. 朴素动态规划长度和计数必须同步转移2.1 状态定义dp 和 cnt 是搭档定义两个数组dp[i]以nums[i]结尾的最长递增子序列长度。cnt[i]以nums[i]结尾的、长度恰好等于dp[i]的递增子序列个数。注意cnt[i]不统计所有以nums[i]结尾的子序列只统计“最长长度”的那些。为什么可以这样因为任意一条全局最长递增子序列如果它不以nums[i]结尾那它和cnt[i]无关如果它确实以nums[i]结尾那它的长度一定等于以nums[i]结尾的最长长度。所以我们把短方案丢掉不会影响最终答案。初始化时每个位置的dp[i] 1表示单个元素本身可以组成长度 1 的递增子序列同时cnt[i] 1因为这种子序列只有一条。2.2 转移规则大于就替换相等就累加从小到大遍历 i对于每个 i再枚举所有 j i。当nums[j] nums[i]时说明nums[i]可以接在以nums[j]结尾的递增子序列后面。这时候分三种情况如果dp[j] 1 dp[i]说明发现了一条更长的路线更新dp[i] dp[j] 1并且cnt[i] cnt[j]。如果dp[j] 1 dp[i]说明又找到了一条和当前最优长度相同的路线执行cnt[i] cnt[j]。如果dp[j] 1 dp[i]说明这条路线不够长忽略。这个规则的直觉是你先找到最长长度把方案数重置为来自该前驱的方案数再遇到同样长度的路线时把方案数累加进去。2.3 手算一个完整例子我用[1, 2, 2, 3]演示一遍这个例子最能暴露问题。i0值 1dp[0]1, cnt[0]1。i1值 2前面只有 012dp[1]从 1 变成 2cnt[1]cnt[0]1。i2值 2前面 j0 的12dp[2]更新为 2cnt[2]1但 j1 的值也是 2不满足严格递增所以不能用。注意这里不能把两个相同值的 2 接起来。i3值 3先看 j013dp[0]12小于当前dp[3]1更新dp[3]2, cnt[3]1。接着 j123dp[1]13大于当前 2更新dp[3]3, cnt[3]cnt[1]1。接着 j223dp[2]13等于当前最优长度 3执行cnt[3]cnt[2]即cnt[3]2。最终全局最大长度max(dp)3把所有dp3的cnt相加得到答案 2。这 2 条分别对应两个不同下标的 2 作为倒数第二个元素虽然数值一样但确实是两条不同的子序列。2.4 代码实现与复杂度def find_number_of_lis(nums): n len(nums) if n 0: return 0 dp [1] * n cnt [1] * n for i in range(n): for j in range(i): if nums[j] nums[i]: if dp[j] 1 dp[i]: dp[i] dp[j] 1 cnt[i] cnt[j] elif dp[j] 1 dp[i]: cnt[i] cnt[j] max_len max(dp) ans 0 for i in range(n): if dp[i] max_len: ans cnt[i] return ans时间复杂度 O(n²)空间复杂度 O(n)。当数组长度在千级到两三千时这个写法足够用。但如果你碰到十万级的数据就必须往下看树状数组的优化。3. 最容易改错的三个细节初始化、重复计数和边界用例3.1 初始化不是全 1 就万事大吉很多人的第一版代码会把cnt初始化为全 1这是对的。但有些人会先给dp全 0然后在转移时用cnt[i] cnt[j]赋值结果漏掉了长度为 1 的基础方案。其实有一个更隐蔽的问题如果dp[i]初始为 1那么在转移时遇到dp[j]1也等于 1 的情况根本不会发生因为dp[j]至少是 1dp[j]1至少是 2。所以初始化为 1 是合理的。真正容易错的是最后收集答案。很多人拿到cnt数组后直接max(cnt)觉得“最长长度对应的方案数”就是答案。但最长长度可能出现在多个不同结尾位置每个位置都贡献一部分方案必须把所有dp[i] max_len的cnt[i]全部加起来。比如[2, 2, 2]每个位置的最长长度都是 1每个cnt都是 1答案不是 1 而是 3。3.2 为什么这样累加不会重复这一步是理解全题的关键。有人会问如果两个不同的前驱 j 最终生成了同一条子序列怎么办不可能。原因很简单一条以nums[i]结尾的子序列它的倒数第二个元素下标必然是某个具体的 j。如果 j 不同就算nums[j]的值相同整条子序列的下标序列也不同所以它们一定是不同子序列。比如[1, 2, 2, 3]里的两条最长序列倒数第二个下标分别是 1 和 2这就是两个不同的序列。那么同一个 j 内部会不会漏算不会。cnt[j]已经统计了所有以 j 结尾、长度等于dp[j]的最优子序列。对每一条在后面接上nums[i]都得到一条不同的新序列。这些新序列之间前缀不同当然不会互相重复。所以累加是安全的。3.3 数组长度为 1 和所有元素相等的极端用例写这个题边界用例必须自己先跑一遍。nums [5]返回 1。nums [5, 5, 5]因为严格递增任何相同值都不能相接所以每个位置都是长度 1 的独立子序列返回 3。nums [5, 4, 3, 2, 1]严格递减同理每个位置都只能作为单元素子序列返回数组长度 n。这些边界用例如果跑错通常说明你的转移条件写成了或者最后统计时把相同值合并了。请记住递增子序列的定义是严格递增等于号是大忌。3.4 计数溢出问题方案数可能非常大尤其是当数组故意构造出很多并列分支时数量会指数级增长。C 里如果用int存cnt很容易溢出。换long long会更稳如果题目要求取模比如和 1e97 取模那就在累加和赋值时都取模。Python 没有溢出问题但在很多实际工程场景中还是要注意数值上限。遇到这种计数题我习惯先用 64 位整数再根据题目要求决定是否取模。4. 树状数组优化到 O(n log n)值域上存“长度计数”4.1 从 O(n²) 到 O(n log n) 的优化思路朴素 DP 慢在哪儿慢在每次处理 i 时都要把所有 j i 扫一遍。但仔细看转移过程我们要找的是所有满足nums[j] nums[i]的 j 中最大的dp[j]是谁以及在这些取到最大dp[j]的 j 身上cnt[j]的总和是多少。换句话说我们需要的是一次“值域上的前缀查询”在数值小于nums[i]的所有已处理元素里查它们的最长长度和对应方案数。如果我们能按数值大小建一个数据结构把已经扫描过的位置按nums[j]的值存进去每次只需要查询前缀区间的聚合信息就能把内层循环的 O(n) 降成 O(log n)。这就是树状数组的切入点。4.2 离散化把数值压缩成有序下标nums里的数值范围可能很大甚至可能有负数直接下标建不了树。所以第一步先排序去重把值映射成 1 到 m 的秩。例如nums [10, 3, 7, 3]去重排序后得到[3, 7, 10]映射关系是3 - 1, 7 - 2, 10 - 3。树状数组长度 m 就是不同数值的个数空间 O(n)。这里有个很关键的细节我们要查的是“严格小于nums[i]的前缀”所以查询的下标是rank(nums[i]) - 1而不是rank(nums[i])。如果查询时把等于当前值的部分也包含进去就会把相同值的方案接在后面变成非严格递增答案立刻错误。我一开始就是在这里栽的。4.3 树状数组节点里存什么普通树状数组每个节点存一个数值的某种聚合这里每个节点要存两个东西len和cnt含义是“该节点管辖的值域范围内以这些值作为结尾时能达到的最长递增子序列长度以及这个长度对应的方案总数”。为什么可以只存最长长度而不保留短长度因为同一个数值可能出现在多个位置这些位置的 dp 值不一定相同。但后续元素想要接在这个值后面时它得到的长度一定等于“以该值结尾的最长长度加 1”。短方案接上去得到的长度永远不可能超过最优方案接上去的结果。所以短方案在这个值上是安全的可以丢掉。不过要注意同一个值如果多个不同位置都达到了当前最长长度它们的方案数必须累加。比如[1, 2, 2, 3]值 2 出现在两个位置且两个位置的 dp 都是 2方案数都是 1。那么值 2 这个桶里最终存的应该是len2, cnt2。这样后续元素 3 查询到值 2 时才能得到 2 条不同的路径。4.4 前缀查询与点更新的实现细节代码里需要实现一个合并函数处理两个二元组(len1, cnt1)和(len2, cnt2)如果len1 len2取第一个。如果len2 len1取第二个。如果长度相等且长度不为 0计数相加。如果两个长度都是 0说明该区间还没有有效状态计数保持 0。树状数组的前缀查询会访问多个互不相交的区间节点把它们的二元组按上述规则合并点更新则沿着树往上走把当前计算出的(cur_len, cur_cnt)合并到经过的每个节点中。from bisect import bisect_left def find_number_of_lis(nums): if not nums: return 0 vals sorted(set(nums)) m len(vals) bit_len [0] * (m 1) bit_cnt [0] * (m 1) def query(i): best_len 0 best_cnt 0 while i 0: if bit_len[i] best_len: best_len bit_len[i] best_cnt bit_cnt[i] elif bit_len[i] best_len and bit_len[i] ! 0: best_cnt bit_cnt[i] i - i -i return best_len, best_cnt def update(i, length, cnt): while i m: if length bit_len[i]: bit_len[i] length bit_cnt[i] cnt elif length bit_len[i] and length ! 0: bit_cnt[i] cnt i i -i for num in nums: idx bisect_left(vals, num) 1 pre_len, pre_cnt query(idx - 1) if pre_len 0: cur_len, cur_cnt 1, 1 else: cur_len, cur_cnt pre_len 1, pre_cnt update(idx, cur_len, cur_cnt) _, ans query(m) return ans我用[1, 2, 2, 3]验证一下这个流程处理第一个 2 时查询小于 2 的前缀得到值 1 的(len1, cnt1)于是算出(len2, cnt1)更新到值 2。处理第二个 2 时同样查询小于 2 的前缀仍然得到(1, 1)算出(2, 1)更新时发现值 2 已经有(2, 1)长度相等所以累加为(2, 2)。处理 3 时查询小于 3 的前缀合并值 1 和值 2 的信息得到(2, 2)于是算出(3, 2)。最终答案 2。这个例子里同一数值的多个位置通过点更新累加计数完美处理了重复值的情况。4.5 完整代码和复杂度分析上面的代码就是完整实现。时间上每个元素做一次查询和一次更新都是 O(log n)所以总复杂度 O(n log n)。空间上树状数组和离散化数组都是 O(n)。相比朴素 DP树状数组方案不只快了一个量级更重要的是它把“位置维度”的枚举转化成了“值域维度”的聚合这种思想在很多类似计数题里都能复用动态规划状态若能写成“前缀最优 计数”往往就能用线段树或树状数组优化。5. 面试追问与变体为什么贪心二分、如何输出路径5.1 为什么贪心二分算法不适合直接计数很多熟悉 LIS 的人第一反应是用经典贪心二分维护tails数组每个长度存一个最小末尾值。这个算法求长度很快但直接用它求个数会遇到一个问题它为了追求 O(n log n)在每个长度上只保留“最小的那个末尾值”丢掉了所有并列末尾值以及它们对应的路径数量。比如[1, 3, 5, 4, 7]在求长度时长度 3 的最小末尾值会保留 4而 5 被丢掉了。但对计数来说5 和 4 都能接到 7 后面构成长度 4这两个都必须保留。所以贪心二分的状态压缩方向是“记录最小末尾值加速比较”不是“记录所有并列方案”直接套上去会严重漏算。如果面试官追问“为什么不用贪心二分”你可以回答贪心二分适合单值比较不适合多方案累积计数需要的是“前缀最大值的数量”树状数组或线段树可以天然维护这种聚合关系。5.2 如果需要输出所有最长递增子序列怎么办有时候题目会升级成“输出所有最长递增子序列”。这时候计数 DP 还不够因为你不仅要数出有几条还要把每条具体序列列出来。一个可行的做法是先用朴素 DP 求出每个位置的dp[i]然后从所有dp[i] max_len的位置触发做 DFS 反向回溯。回溯的时候对于当前位置 i枚举 j i如果满足nums[j] nums[i]且dp[j] 1 dp[i]那么 j 就是一个合法的前驱继续向前递归。注意如果方案数是指数级输出所有序列本身也是指数级任何算法都无法避免。所以这种问题通常只适合小数据量或者题目只要求“方案数”而不是“具体方案”。计数是轻量级的枚举是重量级的两者不能混为一谈。5.3 相关变体非严格递增、最长递减、二维 LIS掌握这个模型后几个变体其实都可以举一反三如果要求非严格递增也就是相等元素可以接在后面转移条件从nums[j] nums[i]改成nums[j] nums[i]树状数组查询时查rank(nums[i])而不是rank(nums[i]) - 1。但要注意此时相同值之间也可以接查询和更新的顺序要小心避免一个元素“自己接自己”。因为我们是先查询再更新所以不会出现同一位置自接的问题。如果要求最长递减子序列的个数可以反转数组然后对反转后的数组求最长递增子序列个数或者把所有数取负再套用递增模板。二维 LIS比如信封嵌套问题通常先按一个维度排序再对另一个维度求 LIS。如果两个维度的值有重复要先处理排序时的相等情况否则会把不该嵌套的信封接在一起。计数逻辑依然沿用“长度 方案数”的思路。这些变体在工程里也有实际对应场景比如事件序列中寻找最长趋势性片段并统计不同趋势片段的个数。理解了这个题你再遇到“最长公共子序列计数”“最长连续子序列计数”这类问题会发现底层逻辑都是相通的。最后说一点个人体会。我第一次独立写这个题用了将近二十分钟才把计数细节理清最大的收获不是记住转移方程而是明白了“最大值唯一时计数很简单最大值并列时计数才是真正的考点”。后来我把树状数组方案也补上对“可合并状态”的理解又上了一个台阶。再遇到类似题目我会先想朴素 DP 状态能不能多带一个cnt再想这个cnt能否用前缀数据结构维护。这套打法在不少计数类动态规划题里都很好用希望也能给你一点启发。