华为 OD 训练营 · 题解精讲
LC673. 最长递增子序列的个数
LC673. 最长递增子序列的个数
题目描述
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。 注意 这个数列必须是 严格 递增的。 示例 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。 提示: 1 <= nums.length <= 2000 -10^6 <= nums[i] <= 10^6
题目解析
解题思路
本题要求计算最长递增子序列（LIS）的个数，而非仅求长度。核心思路是在动态规划求解 LIS 长度的同时，同步维护每个位置作为结尾的 LIS 的个数。
使用两个数组：dp[i] 表示以 nums[i] 结尾的 LIS 长度，count[i] 表示以 nums[i] 结尾的 LIS 的个数。遍历每个位置 i，对于所有 j < i，若 nums[j] < nums[i]，则 nums[i] 可以接在 nums[j] 后面形成更长的递增子序列。此时分两种情况更新 count[i]：
- 若
dp[j] + 1 > dp[i]，说明发现了更长的长度，则dp[i] = dp[j] + 1，且count[i] = count[j]（继承 j 的计数）。 - 若
dp[j] + 1 == dp[i]，说明找到了另一种同样长度的方案，则count[i] += count[j]。
最后，找出全局最大长度 maxLength，将所有 dp[i] == maxLength 的 count[i] 累加即为答案。
关键步骤
1. 初始化：dp = [1]*n，count = [1]*n，每个元素自身构成一个长度为 1 的 LIS。 2. 双重循环：外层 i 从 0 到 n-1，内层 j 从 0 到 i-1。 3. 状态转移：仅当 nums[j] < nums[i] 时更新：
if dp[j]+1 > dp[i]:
dp[i] = dp[j]+1
count[i] = count[j]
elif dp[j]+1 == dp[i]:
count[i] += count[j]4. 统计结果：遍历 dp，累加所有等于 maxLength 的 count[i]。
复杂度分析
- 时间复杂度：O(n²)，两层循环，n ≤ 2000，可接受。
- 空间复杂度：O(n)，两个辅助数组
dp和count。
参考代码
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
# LIS: 最长递增子序列
# 创建一个数组dp，用于存储以每个元素结尾的最长递增序列的长度
dp = [1] * n
# count[i]: 以nums[i]为结尾的LIS的个数
count = [1] * n
# 初始化
maxLength = 1
# 从0开始，填充dp数组
for i in range(n):
for j in range(i):
if nums[i] <= nums[j]:
continue
if dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
count[i] = count[j]
elif dp[i] == dp[j] + 1:
count[i] += count[j]
maxLength = max(maxLength, dp[i])
result = 0
for i in range(n):
if dp[i] == maxLength:
result += count[i]
return result