LeetCode 673. 最长递增子序列的个数
目录
题目描述
题意分析
给定一个整数数组，要求返回「最长严格递增子序列」有多少条，而不是它有多长。子序列允许跳着取，但下标必须保持原有先后顺序，且相邻取出的元素必须严格递增，相等的两个数不能同时出现在一条子序列里。
需要数清楚的只是长度恰好等于最大值的那些子序列，比最长短一截的一概不计。两条子序列只要下标集合不同就算两条，哪怕它们的数值序列完全一样。以
[1, 2, 4, 3]为例，最长长度是 3，[1, 2, 4]和[1, 2, 3]都达到这个长度，答案是 2。约束里数组长度不超过 2000，这个规模明确允许一个平方级的双重循环，不必一上来就追求更优的树状数组或线段树写法；同时题目保证答案能用 32 位整数表示，说明计数虽然可能很大但不需要额外做取模。
边界上要留意：数组长度可能为 1，此时答案是 1；数组里可能全是相同的数，例如
[2, 2, 2, 2]，最长长度是 1，而每一个元素各自构成一条，答案是 4。
解法：长度与数量双状态动态规划
核心思路
只记录 LIS 长度会丢失“有多少种达到该长度”的信息，因此对每个结尾下标同时维护两个状态：
lengths[i]：以nums[i]结尾的最长严格递增子序列长度；counts[i]：以nums[i]结尾、长度恰为lengths[i]的子序列数量。枚举合法前驱
j < i且nums[j] < nums[i]。若lengths[j] + 1更长，旧方案已经不是最优，覆盖长度并将数量重置为counts[j]；若与当前最长长度相等，说明找到了另一批互不重复的下标序列，累加counts[j]。这个转移完整且不重不漏：任何以
i结尾的递增子序列都有唯一的倒数第二个下标j，删掉nums[i]后恰好归入对应前驱的方案集合。最后，最长子序列可能结束在不同位置，需要汇总所有lengths[i]等于全局最大值的counts[i]。
解题步骤
- 每个位置先初始化
lengths[i] = counts[i] = 1，表示只选择当前元素。- 枚举左侧所有严格更小的前驱
j，比较候选长度lengths[j] + 1。- 候选更长时覆盖长度和数量；候选同长时只累加数量。
i的状态确定后，用它更新全局最长长度和答案：更长则重置答案，同长则累加答案。以
[1,3,5,4,7]为例，结尾为 5 和 4 时都得到(长度 3, 数量 1)；处理 7 时，这两批方案都能延长到长度 4，于是数量相加为 2。相反，全相等的[2,2,2]没有合法前驱，每个位置都保持(1,1)，最终答案为 3。
代码实现
class Solution {
public int findNumberOfLIS(int[] nums) {
int n = nums.length;
int[] lengths = new int[n];
int[] counts = new int[n];
int maxLen = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
lengths[i] = 1;
counts[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] >= nums[i]) {
continue;
}
// 更长则覆盖方案数，同长则累加方案数。
if (lengths[j] + 1 > lengths[i]) {
lengths[i] = lengths[j] + 1;
counts[i] = counts[j];
} else if (lengths[j] + 1 == lengths[i]) {
counts[i] += counts[j];
}
}
if (lengths[i] > maxLen) {
maxLen = lengths[i];
ans = counts[i];
} else if (lengths[i] == maxLen) {
ans += counts[i];
}
}
return ans;
}
}
func findNumberOfLIS(nums []int) int {
n := len(nums)
lengths := make([]int, n)
counts := make([]int, n)
maxLen := 0
ans := 0
for i := 0; i < n; i++ {
lengths[i] = 1
counts[i] = 1
for j := 0; j < i; j++ {
if nums[j] >= nums[i] {
continue
}
// 以 j 为前驱时，根据新长度决定覆盖还是累加。
if lengths[j]+1 > lengths[i] {
lengths[i] = lengths[j] + 1
counts[i] = counts[j]
} else if lengths[j]+1 == lengths[i] {
counts[i] += counts[j]
}
}
if lengths[i] > maxLen {
maxLen = lengths[i]
ans = counts[i]
} else if lengths[i] == maxLen {
ans += counts[i]
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n^2)$，每个位置枚举其左侧前驱。
- 空间复杂度：$O(n)$，使用两个长度为
n的状态数组。
关键点总结
- “更优则覆盖、同优则累加”是最优方案计数的核心模式。
counts[i]只统计与当前lengths[i]匹配的方案；长度刷新时旧数量必须作废。- 本题是严格递增，前驱条件必须是
nums[j] < nums[i]。- $n \le 2000$ 时 $O(n^2)$ 动态规划清晰且足够；树状数组方案更复杂，不是面试首选。
易错点总结
- 候选更长时若写成
counts[i] += counts[j]，会把较短方案混入最长方案；此时必须覆盖。- 候选同长时若写成赋值，会漏掉其他前驱贡献；
[1,2,4,3,5]应得到 2。- 使用
nums[j] <= nums[i]会把相等元素接起来；[2,2,2]的答案应是 3，而不是长度为 3 的一条。- 只返回某个最长结尾的数量会漏解；
[1,2,4,3]的两条 LIS 结束位置不同。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 本题的基础版，只求最长长度，可额外用贪心加二分做到 $O(n \log n)$ |
| 354. 俄罗斯套娃信封问题 | 困难 | 二维偏序，难点在先按宽升序、等宽时高降序排序后转化为一维 LIS |
| 368. 最大整除子集 | 中等 | 转移条件从大小比较换成整除关系，且要回溯输出方案本身而非条数 |
| 1048. 最长字符串链 | 中等 | 偏序关系是「删一个字符可得」，需按长度分组并用哈希表加速前驱查找 |
| 面试题 08.13. 堆箱子 | 困难 | 三维严格偏序，三个维度必须同时严格递减才能堆叠 |
| 面试题 17.08. 马戏团人塔 | 中等 | 与 354 同型但数据量更大，几乎强制使用二分优化的 LIS |