LeetCode 673 题解：最长递增子序列的个数（LIS 双状态动态规划）

LeetCode 673 题解：最长递增子序列的个数（LIS 双状态动态规划）

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇题解基于 leetcode 题解仓库中的 problems/673.number-of-longest-increasing-subsequence.md 展开，系统讲解如何用「双状态动态规划」在经典 LIS（最长递增子序列）问题的基础上，额外统计最长递增子序列的个数。读者读完将掌握：为什么单一状态无法统计个数、如何设计dp[i][0]（长度）与dp[i][1]（个数）两个状态并完成转移，以及完整的 Python 实现与复杂度分析，并能把该套路迁移到同类"子序列计数"题目上。

题目描述

给定一个未排序的整数数组，找到最长递增子序列的个数。

• 示例 1：输入[1,3,5,4,7]，输出2。解释：有两个最长递增子序列，分别是[1, 3, 4, 7]和[1, 3, 5, 7]。
• 示例 2：输入[2,2,2,2,2]，输出5。解释：最长递增子序列的长度是 1，并且存在 5 个长度为 1 的子序列，因此输出 5。

注意：给定的数组长度不超过 2000，并且结果一定是 32 位有符号整数。

从示例 2 可以看出，这里要求的是严格递增子序列（相等的元素不能拼接），同时多个同样长的子序列都要被计数。也就是说，本题与仓库中 LIS 专题 selected/LIS.md 里的经典 300 题不同：300 题只问"最长长度"，而本题问的是"达到该最长长度的子序列一共有多少条"。

前置知识：LIS 与动态规划状态定义套路

本题的前置知识是动态规划。在仓库的 thinkings/dynamic-programming.md 中反复强调：定义状态是动态规划的核心，状态定义好了，转移方程与递归树就顺藤摸瓜出来了；字符串类问题的常见套路是dp[i]表示"以 i 结尾的……"。

经典 LIS 正是这一套路的典型应用，其状态定义为：dp[i]表示以nums[i]结尾（一定包含nums[i]）的最长上升子序列长度，答案为max(dp[i])。转移方程为：

dp[i] = dp[j] + 1 (其中 j < i 且 nums[i] > nums[j])

这个方程在 selected/LIS.md 中有详细推导：由于dp[j]一定以nums[j]结尾，nums[j]是其序列中最大的元素，那么只要它后面的nums[i] > nums[j]，nums[i]就能融入dp[j]形成更长序列，长度即dp[j] + 1。该专题还指出，LIS 的 O(N²) 双层循环写法是：

for i in range(n): for j in range(i + 1, n): if nums[j] > nums[i]: # 尝试用 dp[i] 更新 dp[j]

而 673 题正是 selected/LIS.md 中提到的 LIS "换皮题"（该文将其作为滴滴面试题收录）：只把 LIS 的"长度"变成"个数"，骨架依然是动态规划，只是需要多存一个状态。

思路：为什么单一状态不够？

回到本题，题目要求的是最长递增子序列的个数，而非通常的长度。一个自然的想法是：只存储"最长递增子序列的个数"可以吗？

不可以。因为"最长递增子序列的个数"隐式地要求你先知道"最长的递增子序列"是什么——个数是建立在长度之上的信息。如果只存个数而不存长度，当新元素能拼接出更长序列时，你根本无从判断"应该重置个数还是累加个数"。因此，像仓库 selected/LIS.md 中"股票问题"等进阶套路一样，单一状态无法满足条件时，就引入额外状态：一个状态记录长度，另一个状态记录对应长度下的个数。

两个状态的存储方式

一般有两种方式：

1. 二维数组：dp[i][0]表示第一个状态，dp[i][1]表示第二个状态；
2. 两个平行数组：dp1[i]表示第一个状态，dp2[i]表示第二个状态。

两种方式的空间复杂度相同（都是 O(N)），选择哪种看个人习惯。本文采用第一种，且：

• dp[i][0]表示：以nums[i]结尾的最长上升子序列的长度；
• dp[i][1]表示：以nums[i]结尾的、长度为dp[i][0]的子序列的个数。

初始化时每个位置都视为长度为 1、个数为 1 的子序列（即仅包含nums[i]自身的序列）。

状态转移详解

转移过程沿袭 LIS 的常规双循环：遍历到nums[j]时，往前遍历所有满足i < j的i。

• 如果nums[j] <= nums[i]，nums[j]无法和前面任何序列拼接成严格递增子序列，直接跳过（这也是示例 2 中全等数组输出 5 的原因：只有长度为 1 的序列被计数）；
• 否则说明可以拼接。但拼不拼接取决于拼接后是否更长——如果更长了就拼，否则不拼。

在此基础上，为统计个数，需要增加三条转移逻辑（这是本题与经典 LIS 唯一的差别所在）：

1. 拼接后序列更长（dp[i][0] + 1 > dp[j][0]）：说明nums[j]找到了一条新的、更长的递增路径，此时：
   • 更新长度：dp[j][0] = dp[i][0] + 1；
   • 重置个数：dp[j][1] = dp[i][1]（这点容易忽略！因为更长的序列由"以i结尾的所有最优序列"逐一拼接而来，所以个数继承自i，而不是累加）；
   • 同步更新全局最长长度longest = max(longest, dp[j][0])。
2. 拼接后序列一样长（dp[i][0] + 1 == dp[j][0]）：说明这是一条并列的最优路径，个数需要累加：dp[j][1] += dp[i][1]。
3. 拼接后变短：不拼接，不做任何更新。

最终答案不是简单地取某个dp[i][1]，而是要在所有达到最长长度longest的结尾位置处，把个数求和：

sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

完整代码（Python）

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: n = len(nums) # dp[i][0] -> LIS 长度 # dp[i][1] -> 该长度对应的子序列个数 dp = [[1, 1] for _ in range(n)] longest = 1 for i in range(n): for j in range(i + 1, n): if nums[j] > nums[i]: if dp[i][0] + 1 > dp[j][0]: dp[j][0] = dp[i][0] + 1 # 下面这行代码容易忘记，导致出错 dp[j][1] = dp[i][1] longest = max(longest, dp[j][0]) elif dp[i][0] + 1 == dp[j][0]: dp[j][1] += dp[i][1] return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

复杂度分析

令 N 为数组长度。

• 时间复杂度：O(N²)。双层循环枚举所有(i, j)数对，每个数对进行常数次比较与更新。
• 空间复杂度：O(N)。dp数组需要存储 N 个二元组。

对于题目给定的 N ≤ 2000 的限制，O(N²) 完全可行。

关键点解析（易错点）

1. 本质是 LIS 变种：只要理解了经典 LIS 的状态定义与转移（见 selected/LIS.md），本题只是在其上多维护一个"个数"维度，切勿将其当成全新题型。
2. dp[j][1] = dp[i][1]最容易忘记：当发现更长路径时，个数应被继承/重置而非累加。写漏这一行，会导致"个数停留在初始值 1"或错误累加，是本题最典型的出错点。
3. 答案是求和而非取最大值：最长子序列可能以多个不同位置结尾，这些位置的个数需要全部加起来，这正是示例 1 中[1,3,5,4,7]输出 2（两条长度 4 的序列分别以4和5结尾）的原因。

扩展：线段树解法

本题也可以使用线段树（Segment Tree）来求解，并且性能更好——可以做到 O(N log N)。核心思路是以元素值为下标建立线段树，每个节点维护两个值："以该值结尾的 LIS 长度"与该长度对应的个数；对每个nums[i]，查询小于它的最大值区间中"长度最大且并列的个数"来转移。不过线段树属于非本仓库常规解法，且实现复杂度明显更高，因此不在此展开；对数据规模更大、O(N²) 无法通过时，可以考虑这条路。

延伸：把套路迁移到同类题目

本题的"双状态"思想在仓库的 LIS 专题中是一以贯之的套路。selected/LIS.md 指出：LIS 的各类变种（如无重叠区间、最长数对链、用最少数量的箭引爆气球等）本质都是"删除若干元素后剩下的最长严格/非严格递增子序列"，只需要调整比较符号或返回值的转化；而当题目从"求长度"升级为"求方案数/个数"时，思路就是保留长度状态的同时，并行维护一个计数状态，并严格区分转移时的"重置"与"累加"。

若想进一步巩固，可结合 thinkings/dynamic-programming.md 复习状态定义这一核心要素，并在仓库 SUMMARY.md 中找到 673 题（其被收录于中等难度合集 collections/medium.md）的上下文，体会这类"LIS + 计数"题目在刷题路线中的定位。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode