最长递增子序列的个数

本文参考代码随想录

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

示例 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

思路

动态规划

1. 确定dp数组（dp table）以及下标的含义
   dp[i]：i之前（包括i）最长递增子序列的长度为dp[i]
   count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]

2. 确定递推公式
   在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列。那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数，即：count[i] = count[j]。
   在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列。
   那么以i为结尾的子串的最长递增子序列的个数 就应该加上以j为结尾的子串的最长递增子序列的个数，即：count[i] += count[j];

3. dp数组如何初始化
   count[i]记录了以nums[i]为结尾的字符串，最长递增子序列的个数。那么最少也就是1个，所以count[i]初始为1。
   dp[i]记录了i之前（包括i）最长递增序列的长度。最小的长度也是1，所以dp[i]初始为1。

4. 确定遍历顺序
   dp[i] 是由0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。
   j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层

classSolution:deffindNumberOfLIS(self,nums:List[int])->int:size=len(nums)ifsize<=1:returnsize dp=[1]*size count=[1]*size max_length=1foriinrange(size):forjinrange(i):ifnums[i]>nums[j]:ifdp[j]+1>dp[i]:dp[i]=dp[j]+1count[i]=count[j]elifdp[j]+1==dp[i]:count[i]+=count[j]ifdp[i]>max_length:max_length=dp[i]max_count=0foriinrange(size):ifmax_length==dp[i]:max_count+=count[i]returnmax_count