Algorithm

Appearance

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

  • 题号：673
  • 来源：LeetCode
  • 难度：中等
  • 标签：dp 子序列
  • 语言：TypeScript
  • 解法：1 个
  • 作者：lmliheng
  • 最近更新：2026-09-27

TypeScript · O(n^2) 时间 · O(n) 空间 · 更新于 2026-09-27

dp1记长度dp2记个数，等长时累加

typescript
/**
 * @difficulty medium
 * @tags dp,子序列
 * @time O(n^2)
 * @space O(n)
 * @note dp1记长度dp2记个数，等长时累加
 * @673. 最长递增子序列的个数
 */
/**
 * @最长子序列的个数
 * 换个思路
 */

let nums = [1, 3, 5, 4, 7]
let n = nums.length
if (n <= 1) {
    n
}
let max = 0
let res = 0
// dp1[i]表示最长递增子序列的长度，dp2[i]表示dp1[i]长度子序列的个数
let dp1 = new Array(n).fill(0)
let dp2 = new Array(n).fill(0)
for (let i = 0; i < n; i++) {
    dp1[i] = 1
    dp2[i] = 1
    for (let j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
            if (dp1[j] + 1 > dp1[i]) {
                dp1[i] = dp1[j] + 1
                dp2[i] = dp2[j]
            }

            else if (dp1[j] + 1 === dp1[i]) {
                dp2[i] += dp2[j]
            }
        }

    }
    if (dp1[i] > max) {
        max = dp1[i]
        res = dp2[i]
    } else if (dp1[i] === max) {
        res += dp2[i]
    }

}
console.log(res)

源码：ts/leetcode/673. 最长递增子序列的个数.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm