LeetCode 673. 最长递增子序列的个数

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 673. 最长递增子序列的个数

思路分析

解法一：动态规划（推荐）

核心思路：

维护两个数组：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度，cnt[i] 表示以 nums[i] 结尾的最长递增子序列个数。

初始时每个元素自身构成长度为 1 的子序列，因此 dp[i] = 1，cnt[i] = 1。

对于每个 i，枚举所有 j < i 且 nums[j] < nums[i]，进行状态转移：

若 dp[j] + 1 > dp[i]：发现更长的子序列，更新 dp[i] = dp[j] + 1，并重置 cnt[i] = cnt[j]。

若 dp[j] + 1 == dp[i]：发现等长的子序列，累加方案数 cnt[i] += cnt[j]。

最后遍历所有 dp[i]，找到最大长度 maxLen，将所有满足 dp[i] == maxLen 的 cnt[i] 累加即为答案。

复杂度分析：

时间复杂度：O(n²)，其中 n 为数组长度，双重循环枚举所有 (j, i) 对。

空间复杂度：O(n)，其中 n 为数组长度，需要两个长度为 n 的辅助数组。

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
        int[] dp = new int[n];
        // cnt[i] 表示以 nums[i] 结尾的最长递增子序列个数
        int[] cnt = new int[n];

        // 每个元素自身可以构成长度为 1 的递增子序列
        Arrays.fill(dp, 1);
        Arrays.fill(cnt, 1);

        int maxLen = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                // nums[j] < nums[i] 时，nums[i] 可以接在 nums[j] 后面
                if (nums[j] < nums[i]) {
                    // 发现更长的递增子序列，更新长度并重置方案数
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    // 发现等长的递增子序列，累加方案数
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }

        // 统计所有以最长递增子序列长度结尾的方案数之和
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) {
                result += cnt[i];
            }
        }
        return result;
    }
}

func findNumberOfLIS(nums []int) int {
    n := len(nums)
    // dp[i] 表示以 nums[i] 结尾的最长递增子序列长度
    dp := make([]int, n)
    // cnt[i] 表示以 nums[i] 结尾的最长递增子序列个数
    cnt := make([]int, n)

    // 每个元素自身可以构成长度为 1 的递增子序列
    for i := range dp {
        dp[i] = 1
        cnt[i] = 1
    }

    maxLen := 1

    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            // nums[j] < nums[i] 时，nums[i] 可以接在 nums[j] 后面
            if nums[j] < nums[i] {
                // 发现更长的递增子序列，更新长度并重置方案数
                if dp[j]+1 > dp[i] {
                    dp[i] = dp[j] + 1
                    cnt[i] = cnt[j]
                // 发现等长的递增子序列，累加方案数
                } else if dp[j]+1 == dp[i] {
                    cnt[i] += cnt[j]
                }
            }
        }
        if dp[i] > maxLen {
            maxLen = dp[i]
        }
    }

    // 统计所有以最长递增子序列长度结尾的方案数之和
    result := 0
    for i := 0; i < n; i++ {
        if dp[i] == maxLen {
            result += cnt[i]
        }
    }
    return result
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	动态规划 / 二分优化
354. 俄罗斯套娃信封问题	困难	动态规划 / 二分优化 LIS
1143. 最长公共子序列	中等	动态规划 / 字符串
368. 最大整除子集	中等	动态规划 / LIS 变形
646. 最长数对链	中等	动态规划 / 贪心 / 区间排序
1626. 无矛盾的最佳球队	中等	动态规划 / LIS 变形
1048. 最长字符串链	中等	动态规划 / LIS 变形

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/85984966