最长递增子序列的个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

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

提示:

• 1 <= nums.length <= 2000
• -10<sup>6</sup> <= nums[i] <= 10<sup>6</sup>

思路：要掌握这道题，确实需要先掌握 300. 最长递增子序列 这道题，因为你只有知道了怎么得到最长递增子序列，才能进一步计算个数，最开始不知道如何用dp进一步求个数，一直没有思路，看了一眼答案，说用另外一个数组存以数组某个元素结尾的最长递增子序列的个数，假设为 cnt [ ], 那么就是在计算 dp [ ] （最长递增子序列长度） 的同时维护 个数。这么想来确实可以操作了， 把 300 题中 dp[ i ] = max(dp[ j ] + 1, dp[ i ]) 的条件需要拆开，因为一旦发现更长的子序列，就要把 cnt[ i ] 更新成 cnt[ j ] ， 这样写起代码却总是不通过，先看按照这个思路的第一版代码

        if not nums:
            return 0
        n = len(nums)
        if n == 1:
            return 1
        dp = cnt = [1] * n （问题1）
        maxLen, maxCnt = 0, 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j] + 1 > dp[i]:
                        cnt[i] = cnt[j]
                        dp[i] = dp[j] + 1
                    elif dp[j] + 1 == dp[i]:
                        cnt[i] += 1 （问题2）
            if dp[i] > maxLen:
                maxLen = dp[i]
                maxCnt = cnt[i]
            elif dp[i] == maxLen:
                maxCnt += 1 （问题3）
        return maxCnt

这里有几个坑自己没过，后来问了gpt 或者自己想出来的，就是我标有问题的地方
问题1 ：python中如果这样给两个数组赋值的话，他们指向的同一片内存空间，所以最后的结果一直不对
问题2：既然知道发现更长的子序列，就要把 cnt[ i ] 更新成 cnt[ j ] ， 那么当 dp[j] + 1 == dp[i] 时候，cnt [ i ] 要加上的是 cnt[j] 啊，怎么会是 1 呢
问题3： 其实和问题2一样，第一个if 条件中知道会更新成 cnt[ j ] 第二个条件就是 += cnt [ j ] 啊，怎么会是1 呢

问题1 属于对于python 不够熟悉
问题2 3 就是在写每一个地方的时候都要好好想想 应该加什么值，加1 是对的吗？

上一个更新之后的代码

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # dp[i]表示以nums[i]结尾的最长递增子序列的长度
        # cnt[i]表示以nums[i]结尾的最长递增子序列的个数
        if not nums:
            return 0

        n = len(nums)
        if n == 1:
            return 1
        dp, cnt = [1] * n, [1] * n
        maxLen, maxCnt = 0, 0
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j] + 1 > dp[i]:
                        cnt[i] = cnt[j]
                        dp[i] = dp[j] + 1
                    elif dp[j] + 1 == dp[i]:
                        cnt[i] += cnt[j]
            if dp[i] > maxLen:
                maxLen = dp[i]
                maxCnt = cnt[i]
            elif dp[i] == maxLen:
                maxCnt += cnt[i]
        return maxCnt