线性动态规划：最长递增子序列的变种——最长递增子序列的个数 题目描述： 给定一个整数数组 nums，找到最长递增子序列（LIS）的长度，并统计具有该长度的不同递增子序列的个数。注意：子序列不要求连续，但必须保持原数组中的相对顺序，且严格递增（不能有相等元素）。 解题过程： 问题分析： 我们需要解决两个问题：找到最长递增子序列的长度，以及统计具有这个长度的不同递增子序列的数量 这是一个经典的动态规划问题，需要设计两个DP数组 定义DP状态： 定义 length[i] 表示以第 i 个元素结尾的最长递增子序列的长度 定义 count[i] 表示以第 i 个元素结尾的、长度为 length[i] 的递增子序列的个数 状态转移方程： 对于每个位置 i（从 0 到 n-1）： 初始化： length[i] = 1 ， count[i] = 1 （单独一个元素本身就是一个子序列） 对于所有 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] 寻找最终结果： 找出最大的 LIS 长度 maxLen 将所有 length[i] == maxLen 的 count[i] 累加，得到总个数 示例演示： 考虑数组 nums = [ 1, 3, 5, 4, 7 ] i=0: length[ 0]=1, count[ 0 ]=1 i=1: j=0: 1<3 → length[ 1]=2, count[ 1 ]=1 i=2: j=0: 1 <5 → length=2, count=1 j=1: 3 <5 → length=3, count=1 i=3: j=0: 1 <4 → length=2, count=1 j=1: 3 <4 → length=3, count=1 i=4: j=0: 1 <7 → length=2, count=1 j=1: 3 <7 → length=3, count=1 j=2: 5 <7 → length=4, count=1 j=3: 4<7 → length=4, count=1 → 累加 count[ 4 ]=2 最长长度 = 4，个数 = 1 + 2 = 3 具体序列：[ 1,3,5,7], [ 1,3,4,7], [ 1,3,5,7 ]（注意第三个与第一个相同） 时间复杂度优化： 基础解法时间复杂度 O(n²)，空间复杂度 O(n) 可以使用二分查找优化到 O(n log n)，但会丢失计数信息 边界情况处理： 空数组返回 (0, 0) 所有元素相等时，最长递增子序列长度为1，个数为数组长度 严格递减数组，最长递增子序列长度为1，个数为数组长度 这个解法清晰地展示了如何同时求解最长递增子序列的长度和个数，是线性动态规划的典型应用。