# 0673. 最长递增子序列的个数

### 题目地址(673. 最长递增子序列的个数)

<https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/>

### 题目描述

```
给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

```

### 前置知识

* 动态规划

### 公司

* 暂无

### 思路

这道题其实就是 **最长上升子序列（LIS）** 的变种题。如果对 LIS 不了解的可以先看下我之前写的一篇文章[穿上衣服我就不认识你了？来聊聊最长上升子序列](https://lucifer.ren/blog/2020/06/20/LIS/)，里面将这种题目的套路讲得很清楚了。

回到这道题。题目让我们求最长递增子序列的个数，而不是通常的**最长递增子序列的长度**。 因此我想到使用另外一个变量记录**最长递增子序列的个数**信息即可。类似的套路有**股票问题**，这种问题的套路在于只是单独存储一个状态以无法满足条件，对于这道题来说，我们存储的单一状态就是**最长递增子序列的长度**。那么一个自然的想法是**不存储最长递增子序列的长度，而是仅存储最长递增子序列的个数**可以么？这是不可以的，因为**最长递增子序列的个数** 隐式地条件是你要先找到最长的递增子序列才行。

如何存储两个状态呢？一般有两种方式：

* 二维数组 dp\[i]\[0] 第一个状态 dp\[i]\[1] 第二个状态
* dp1\[i] 第一个状态 dp2\[i] 第二个状态

使用哪个都可以，空间复杂度也是一样的，使用哪种看你自己。这里我们使用第一种，并且 dp\[i]\[0] 表示 以 nums\[i] 结尾的最长上升子序列的长度，dp\[i]\[1] 表示 以 nums\[i] 结尾的长度为 dp\[i]\[0] 的子序列的个数。

明确了要多存储一个状态之后，我们来看下状态如何转移。

LIS 的一般过程是这样的：

```py
for i in range(n):
    for j in range(i + 1, n):
        if nums[j] > nums[i]:
            # ...
```

这道题也是类似，遍历到 nums\[j] 的时候往前遍历所有的 满足 i < j 的 i。

* 如果 nums\[j] <= nums\[i]， nums\[j] 无法和前面任何的序列拼接成**递增子序列**
* 否则说明我们可以拼接。但是拼接与否取决于拼接之后会不会更长。如果更长了就拼，否则不拼。

上面是 LIS 的常规思路，下面我们加一点逻辑。

* 如果拼接后的序列更长，那么 dp\[j]\[1] = dp\[i]\[1] （这点容易忽略）
* 如果拼接之后序列一样长， 那么 dp\[j]\[1] += dp\[i]\[1]。
* 如果拼接之后变短了，则不应该拼接。

### 关键点解析

* [最长上升子序列问题](https://lucifer.ren/blog/2020/06/20/LIS/)
* dp\[j]\[1] = dp\[i]\[1] 容易忘记

### 代码

代码支持: Python

```py
class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i][0] ->  LIS
        # dp[i][1] -> NumberOfLIS
        dp = [[1, 1] for _ in range(n)]
        longest = 1
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0] + 1
                        # 下面这行代码容易忘记，导致出错
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])
                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
        return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

```

**复杂度分析**

令 N 为数组长度。

* 时间复杂度：$O(N^2)$
* 空间复杂度：$O(N)$

### 扩展

这道题也可以使用线段树来解决，并且性能更好，不过由于不算是常规解法，因此不再这里展开，感兴趣的同学可以尝试一下。

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/9annlp.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/673.number-of-longest-increasing-subsequence.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.