673. 最长递增子序列的个数
Difficulty
Medium
Tags
动态规划
Star
❤
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 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位有符号整数。
法1 动态规划
思路
在300. 最长递增子序列的基础上多使用一个数组来记录LIS的组合数。直白来说就是，当更新dp的时候 同时记录组合数。
题解
class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: dp = [1 for _ in range(len(nums))] count = [1 for _ in range(len(nums))] for i in range(1, len(dp)): for j in range(0, i): if nums[i] > nums[j]: # 更新dp的时候，不能简单取max,而要同时更新count if dp[i] < dp[j] + 1: # 如果+1等于当前LIS 则说明找到了新组合 dp[i] = dp[j] + 1 count[i] = count[j] elif dp[i] == dp[j] + 1: # 如果+1长于当前LIS 则组合数不变 count[i] += count[j] # 取得最大递增子序列长度 maxVal = max(dp) # 统计最大长度的组合数 res = 0 for i in range(0, len(count)): if maxVal == dp[i] : res += count[i] return res