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 中股票问题等进阶套路一样单一状态无法满足条件时就引入额外状态一个状态记录长度另一个状态记录对应长度下的个数。两个状态的存储方式一般有两种方式二维数组dp[i][0]表示第一个状态dp[i][1]表示第二个状态两个平行数组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 唯一的差别所在拼接后序列更长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])。拼接后序列一样长dp[i][0] 1 dp[j][0]说明这是一条并列的最优路径个数需要累加dp[j][1] dp[i][1]。拼接后变短不拼接不做任何更新。最终答案不是简单地取某个dp[i][1]而是要在所有达到最长长度longest的结尾位置处把个数求和sum(dp[i][1] for i in range(n) if dp[i][0] longest)完整代码Pythonclass 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²) 完全可行。关键点解析易错点本质是 LIS 变种只要理解了经典 LIS 的状态定义与转移见 selected/LIS.md本题只是在其上多维护一个个数维度切勿将其当成全新题型。dp[j][1] dp[i][1]最容易忘记当发现更长路径时个数应被继承/重置而非累加。写漏这一行会导致个数停留在初始值 1或错误累加是本题最典型的出错点。答案是求和而非取最大值最长子序列可能以多个不同位置结尾这些位置的个数需要全部加起来这正是示例 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考