【LeetCode】动态规划—673. 最长递增子序列的个数（附完整Python/C++代码）

class Solution:
    def findNumberOfLIS(self, nums):
        if not nums:
            return 0

        n = len(nums)
        dp = [1] * n  # 初始化 dp 数组
        count = [1] * n  # 初始化 count 数组

        for i in range(n):  # 遍历每个元素
            for j in range(i):  # 检查前面的元素
                if 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]  # 累加个数

        max_length = max(dp)  # 获取最长递增子序列的长度
        return sum(count[i] for i in range(n) if dp[i] == max_length)  # 返回该长度的个数

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;

        int n = nums.size();
        vector<int> dp(n, 1);  // dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度
        vector<int> count(n, 1);  // count[i] 表示以 nums[i] 结尾的最长上升子序列的个数
        int max_length = 0;  // 记录最长上升子序列的长度
        int max_count = 0;   // 记录最长上升子序列的个数

        // 动态规划计算 dp 和 count 数组
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;  // 更新长度
                        count[i] = count[j]; // 更新个数
                    } else if (dp[j] + 1 == dp[i]) {
                        count[i] += count[j]; // 追加个数
                    }
                }
            }
            max_length = max(max_length, dp[i]); // 更新最大长度
        }

        // 计算最长上升子序列的总个数
        for (int i = 0; i < n; ++i) {
            if (dp[i] == max_length) {
                max_count += count[i]; // 统计个数
            }
        }

        return max_count; // 返回结果
    }
};