最长递增子序列的个数

题目描述
给定一个整数数组 nums，找到最长递增子序列（LIS）的长度，并返回不同最长递增子序列的个数。注意：序列必须是严格递增的，且两个序列被视为不同，只要它们选取的元素下标不同（即使元素值相同）。

解题思路
这个问题需要同时解决两个问题：

1. 找到最长递增子序列的长度
2. 统计所有最长递增子序列的数量

我们需要设计一个动态规划方案，既能记录每个位置结尾的最长递增子序列长度，又能记录对应的序列数量。

详细解题步骤

步骤1：定义状态
我们定义两个数组：

• length[i]：表示以第i个元素结尾的最长递增子序列的长度
• count[i]：表示以第i个元素结尾的最长递增子序列的个数

步骤2：状态初始化
对于每个位置i，初始时：

• length[i] = 1（最短的递增子序列就是只包含自己）
• count[i] = 1（只有一种方式：只选择自己）

步骤3：状态转移方程
对于每个位置i，我们需要检查所有j < i：

• 如果nums[j] < nums[i]（满足递增条件）：
  • 如果length[j] + 1 > length[i]：
    • 更新length[i] = length[j] + 1
    • 重置count[i] = count[j]
  • 如果length[j] + 1 == length[i]：
    • 累加count[i] += count[j]

步骤4：寻找全局最优
遍历完成后，我们需要：

1. 找到最大的length[i]值（即最长递增子序列的长度）
2. 将所有length[i]等于最大长度的count[i]累加起来

步骤5：示例演示
以数组[1, 3, 5, 4, 7]为例：

初始化：

• length = [1, 1, 1, 1, 1]
• count = [1, 1, 1, 1, 1]

处理过程：

• i=0：第一个元素，保持不变
• i=1：比较nums[0]=1 < nums[1]=3
  • length[1] = max(1, 1+1) = 2
  • count[1] = count[0] = 1
• i=2：比较前两个元素
  • nums[0]=1 < 5：length[2] = 2, count[2] = 1
  • nums[1]=3 < 5：length[2] = 3, count[2] = 1
• i=3：比较前三个元素
  • nums[0]=1 < 4：length[3] = 2, count[3] = 1
  • nums[1]=3 < 4：length[3] = 3, count[3] = 1
  • nums[2]=5 > 4：不满足条件
• i=4：比较前四个元素
  • nums[0]=1 < 7：length[4] = 2, count[4] = 1
  • nums[1]=3 < 7：length[4] = 3, count[4] = 1
  • nums[2]=5 < 7：length[4] = 4, count[4] = 1
  • nums[3]=4 < 7：length[4] = 4, count[4] = 2

最终结果：

• 最大长度：4
• 总数量：count[4] = 2

步骤6：算法实现

def findNumberOfLIS(nums):
    if not nums:
        return 0
    
    n = len(nums)
    length = [1] * n  # 以i结尾的最长递增子序列长度
    count = [1] * n   # 以i结尾的最长递增子序列数量
    
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if length[j] + 1 > length[i]:
                    length[i] = length[j] + 1
                    count[i] = count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]
    
    max_length = max(length)
    result = 0
    for i in range(n):
        if length[i] == max_length:
            result += count[i]
    
    return result

时间复杂度分析

• 时间复杂度：O(n²)，需要两层循环遍历
• 空间复杂度：O(n)，需要两个长度为n的数组

这个算法通过动态规划同时跟踪长度和数量，有效地解决了最长递增子序列的计数问题。