最长递增子序列的变种：最长递增子序列的个数（进阶版——允许重复元素） 题目描述： 给定一个整数数组 nums，找到最长递增子序列（LIS）的长度，并统计最长递增子序列的个数。注意：这个数组可能包含重复元素。你需要返回最长递增子序列的个数。 解题过程： 问题分析： 我们需要找到所有最长递增子序列的数量 数组可能包含重复元素，这意味着不同的位置可能产生相同的数值序列 我们需要确保统计的是不同的索引序列（即使数值相同但位置不同也算不同的子序列） 动态规划状态定义： 定义 dp_ len[ i]：以 nums[ i ] 结尾的最长递增子序列的长度 定义 dp_ count[ i]：以 nums[ i ] 结尾的最长递增子序列的个数 状态转移方程： 对于每个位置 i，我们需要检查所有 j < i 如果 nums[ j] < nums[ i ]： 如果 dp_ len[ j] + 1 > dp_ len[ i]：更新 dp_ len[ i] 和 dp_ count[ i ] 如果 dp_ len[ j] + 1 == dp_ len[ i ]：累加计数 如果 nums[ j] == nums[ i ]：需要特殊处理避免重复计数 处理重复元素的策略： 当遇到 nums[ j] == nums[ i ] 时，我们需要确保不重复统计 策略：只有当 j 和 i 对应的最长递增子序列长度相同时，才考虑合并计数 算法步骤： a. 初始化两个数组，长度都为 n b. 遍历每个位置 i（从 0 到 n-1） c. 对于每个 i，遍历所有 j < i d. 根据数值关系更新状态 e. 最后统计所有达到最大长度的位置的数量总和 具体实现细节： 需要维护当前找到的最大长度 max_ len 最后遍历所有位置，将 dp_ len[ i] == max_ len 的 dp_ count[ i ] 累加 时间复杂度：O(n²)，空间复杂度：O(n) 这个算法通过同时维护长度和计数信息，并妥善处理重复元素的情况，能够正确统计最长递增子序列的个数。