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

约 5 分钟
文章信息 13 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 腾讯 字节 美团 拼多多 百度 快手 滴滴 猿辅导
标签
数组 动态规划 线段树 树状数组

题目描述

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

image-20260928203304633

题意分析

从数组中按下标递增的顺序选择元素，允许跳过元素，要求选中的值严格递增。先确定能够达到的最长长度，再统计恰好具有这个长度的子序列有多少条。

统计的是下标选择方案：即使选出的数值相同，只要使用的位置不同，也属于不同子序列。相等的值不能接在一起形成递增，但各自仍可贡献独立方案；答案不是最长长度本身，也不是所有递增子序列的总数。

解法：长度与数量双状态动态规划

核心思路

[!blue]

同一个结尾位置可能对应许多递增子序列，只保存长度无法知道有多少条最优选择。因此同时维护 lengths[i] 与 counts[i]：前者表示必须以 i 结尾的最大长度，后者只统计达到这个长度的方案数。

每个位置先取状态 (1, 1)，表示只选择当前元素。要延长到 i，前一个下标必须满足 j < i 且 nums[j] < nums[i]。以 j 结尾的每条最长方案都能追加当前元素，形成候选长度 lengths[j] + 1，方案数为 counts[j]。

候选长度更长时，当前保存的旧方案已经不是最优，必须同时替换长度和数量；候选同长时，两批方案都达到最优，应累加数量；候选更短则忽略。不同前驱 j 贡献的方案，倒数第二个下标不同，所以相加不会重复计数。

枚举完全部前驱后，i 的状态才最终确定。再与全局最长长度比较：更长就把全局数量重置为 counts[i]，同长就累加。不同结尾的方案最后一个下标不同，因此全局相加同样不会重复；只返回某一个结尾的数量则会漏掉其他最优方案。

解题步骤

  1. 创建长度和计数数组，初始化全局最长长度 maxLen = 0、数量 ans = 0。
  2. 从左到右处理位置 i，先令 lengths[i] = counts[i] = 1。
  3. 枚举左侧位置 j，跳过数值不小于当前值的前驱。
  4. 比较 lengths[j] + 1：更长则替换当前长度和计数，同长则只累加 counts[j]。
  5. 当前结尾处理完后，用同样的“更长替换、同长累加”规则更新全局状态。
  6. 返回 ans，即全局最长长度对应的全部下标方案数。

代码实现

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] lengths = new int[n];
        int[] counts = new int[n];
        int maxLen = 0;
        int ans = 0;

        for (int i = 0; i < n; i++) {
            lengths[i] = 1;
            counts[i] = 1;

            for (int j = 0; j < i; j++) {
                if (nums[j] >= nums[i]) {
                    continue;
                }

                // 更长则覆盖方案数，同长则累加方案数。
                if (lengths[j] + 1 > lengths[i]) {
                    lengths[i] = lengths[j] + 1;
                    counts[i] = counts[j];
                } else if (lengths[j] + 1 == lengths[i]) {
                    counts[i] += counts[j];
                }
            }

            if (lengths[i] > maxLen) {
                maxLen = lengths[i];
                ans = counts[i];
            } else if (lengths[i] == maxLen) {
                ans += counts[i];
            }
        }

        return ans;
    }
}

func findNumberOfLIS(nums []int) int {
    n := len(nums)
    lengths := make([]int, n)
    counts := make([]int, n)
    maxLen := 0
    ans := 0

    for i := 0; i < n; i++ {
        lengths[i] = 1
        counts[i] = 1
        for j := 0; j < i; j++ {
            if nums[j] >= nums[i] {
                continue
            }
            // 以 j 为前驱时，根据新长度决定覆盖还是累加。
            if lengths[j]+1 > lengths[i] {
                lengths[i] = lengths[j] + 1
                counts[i] = counts[j]
            } else if lengths[j]+1 == lengths[i] {
                counts[i] += counts[j]
            }
        }

        if lengths[i] > maxLen {
            maxLen = lengths[i]
            ans = counts[i]
        } else if lengths[i] == maxLen {
            ans += counts[i]
        }
    }
    return ans
}

复杂度分析

  • 时间复杂度：$O(n^2)$，每个位置最多枚举此前所有下标，比较总数为 $n(n-1)/2$。
  • 空间复杂度：$O(n)$，两个状态数组各保存 n 个位置的信息。

关键点总结

[!green]

  • “以当前位置结尾”明确了状态的最后一个下标，便于从所有合法前驱延长。
  • 计数必须始终与当前最优长度绑定，长度变长时旧计数作废。
  • 同长方案按不同前驱分组累加，最终再按不同结尾分组累加，两层分组都互不重叠。
  • 下标不同即可算不同方案，不应因为值重复而去重。

易错点总结

[!yellow]

  • 候选更长时仍累加旧数量，会把较短子序列算入当前最长方案。
  • 候选同长时直接覆盖数量，会丢掉其他前驱带来的同长度方案。
  • 将前驱判断写成允许相等，求出的会是非递减子序列，偏离严格递增要求。
  • 计数初始为零，忽略单个元素本身也是一条长度一的子序列。
  • 当前结尾的前驱尚未处理完就反复累加全局答案，可能重复统计尚未确定的状态。
  • 最后只取计数数组中的最大值，不能代表所有最长子序列的总数；应按最大长度汇总。

相似题目

题目 难度 关联与区别
300. 最长递增子序列 中等 在LIS长度之外维护达到该长度的方案数，遇到同长最优前驱要累加而非覆盖。
674. 最长连续递增序列 简单 原题只求连续递增段，本题允许跳过元素并统计所有最长选择。
354. 俄罗斯套娃信封问题 困难 用以当前元素结尾的递增状态或最小尾值优化；本题同时记录最优长度与达到该长度的方案数，该题先处理二维排序及等宽冲突。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/85984966
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！