最长递增子序列的变种：最长递增子序列的个数 题目描述 给定一个整数数组 nums ，我们需要找出最长递增子序列（LIS）的长度，并统计所有可能的最长递增子序列的个数。注意，子序列不要求连续，但必须严格递增。例如，对于输入 [1,3,5,4,7] ，最长递增子序列的长度是 4（如 [1,3,4,7] 和 [1,3,5,7] ），因此最长递增子序列的个数是 2。 解题过程 问题分析 基础问题：使用动态规划求最长递增子序列长度。定义 dp_len[i] 表示以 nums[i] 结尾的最长递增子序列长度。 新增目标：统计最长递增子序列的个数。需要额外定义 dp_count[i] 表示以 nums[i] 结尾的最长递增子序列的个数。 状态定义 dp_len[i] ：以 nums[i] 结尾的 LIS 长度。 dp_count[i] ：以 nums[i] 结尾的 LIS 的个数。 状态转移 初始化：每个元素自身构成长度为 1 的子序列，因此 dp_len[i] = 1 ， dp_count[i] = 1 。 遍历 i 从 0 到 n-1，对于每个 i ，遍历 j 从 0 到 i-1： 如果 nums[j] < nums[i] ，说明 nums[i] 可以接在以 nums[j] 结尾的子序列后： 若 dp_len[j] + 1 > dp_len[i] ：更新 dp_len[i] = dp_len[j] + 1 ，并重置 dp_count[i] = dp_count[j] 。 若 dp_len[j] + 1 == dp_len[i] ：说明找到相同长度的新路径，累加个数， dp_count[i] += dp_count[j] 。 统计结果 遍历所有 dp_len[i] ，找到最大值 max_len 。 将所有 dp_len[i] == max_len 对应的 dp_count[i] 相加，得到最长递增子序列的总个数。 示例演算 （以 nums = [1,3,5,4,7] 为例） 初始化： dp_len = [1,1,1,1,1] , dp_count = [1,1,1,1,1] 。 i=1（元素3）： j=0（1<3）： dp_len[1]=2 , dp_count[1]=1 。 i=2（元素5）： j=0（1<5）： dp_len[2]=2 , dp_count[2]=1 。 j=1（3<5）： dp_len[2]=3 （更新）, dp_count[2]=1 。 i=3（元素4）： j=0（1<4）： dp_len[3]=2 , dp_count[3]=1 。 j=1（3<4）： dp_len[3]=3 （更新）, dp_count[3]=1 。 j=2（5≥4，跳过）。 i=4（元素7）： j=0（1<7）： dp_len[4]=2 , dp_count[4]=1 。 j=1（3<7）： dp_len[4]=3 , dp_count[4]=1 。 j=2（5<7）： dp_len[4]=4 （更新）, dp_count[4]=1 。 j=3（4<7）： dp_len[4]=4 （相同长度）, dp_count[4]=1+1=2 。 最终： max_len=4 ，对应 i=4 的 dp_count[4]=2 ，故答案为 2。 复杂度分析 时间复杂度：O(n²)，需要双层循环遍历所有元素对。 空间复杂度：O(n)，用于存储两个 dp 数组。 通过以上步骤，我们同时得到了最长递增子序列的长度和个数。