673 最长递增子序列的个数（动态规划-最长上升子序列）

雨点打透心脏的1/2处 2022-09-02 12:51 171阅读 0赞

**1. 问题描述：**

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

**示例 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位有符号整数。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence

**2. 思路分析：**

这道题目与力扣的[300][]题是类似的，这道题目多了一个需要维护的信息：最长上升子序列的个数，我们只需要在求解最长上升子序列的过程中维护对应的个数即可，这里可以使用g数组来维护这个信息，其中g\[i\]表示以i结尾的最长递增子序列的数目，如何更新g\[i\]的值呢？我们在求解最长子序列的过程中主要分为两种情况来更新当前的g\[i\]：

*  当前的数字nums\[i\]接在了某个nums\[j\]的后面发现可以构成更长的递增子序列，也即f\[i\] < f\[j\] + 1，说明这个时候需要更新g\[i\]和f\[i\]，g\[i\] = g\[j\]，f\[i\] = f\[j\] + 1,
 *  当前的数字nums\[i\]接在了某个nums\[j\]后面发现构成的递增子序列长度等于f\[i\]，也即f\[j\] + 1 = f\[i\]，说明这个时候只需要更新g\[i\]，g\[i\] += g\[j\]

我们可以声明一个变量l来记录遍历过程中的最长递增子序列的长度，当发现以当前以i结尾的子序列是更长之后那么需要更新一下答案res和当前最长递增子序列的长度l，相等的时候那么更新一下答案res即可。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def findNumberOfLIS(self, nums: List[int]) -> int:
            n = len(nums)
            # f[i]表示以i结尾的最长子序列的长度, g[i]表示以i结尾的最长子序列的个数
            f, g = [0] * n, [0] * n
            # l为当前最长子序列的长度
            l, res = 0, 0
            for i in range(n):
                # 一开始的时候都为1
                f[i], g[i] = 1, 1
                for j in range(i):
                    if nums[i] > nums[j]:
                        # 这里需要判断两种情况
                        if f[j] + 1 > f[i]:
                            f[i] = f[j] + 1
                            g[i] = g[j]
                        elif f[j] + 1 == f[i]:
                            g[i] += g[j]
                # 判断当前子序列的长度是否更长了如果更长那么更新答案和当前最长的子序列的长度
                if l < f[i]:
                    l = f[i]
                    res = g[i]
                elif l == f[i]:
                    res += g[i]
            return res

[300]: https://blog.csdn.net/qq_39445165/article/details/109343916