动态规划：力扣673. 最长递增子序列的个数

1、题目描述：

2、题解：

可以参考动态规划或贪心+二分查找：力扣300. 最长上升子序列，比其多了一个状态。 方法1：动态规划：

动态规划问题，弄清楚三点：

1、重复子问题； 2、最优子结构； 3、无后效性。 动态规划：

1、状态定义； 2、状态转移方程； 3、初始化；base case 4、输出； 5、思考状态压缩。 可以用递归去求，但是会存在重叠子问题，加个备忘录可以解决重复问题。

状态定义： lengths[i],以nums[i]结尾的最长递增子序列长度 count[i],以nums[i]结尾的最长递增子序列的个数/组合数量 状态转移方程： if nums[j] < nums[i]: if lengths[j] + 1 > lengths[i]: lengths[i] = max(lengths[i], lengths[j] + 1) counts[i] = counts[j] elif lengths[j] + 1 == lengths[i]: counts[i] += counts[j] 解释：当j < i ,且nums[j] < nums[i]时，如果lengths[j] + 1 > lengths[i]，说明是第一次找到以nums[i]结尾 的且长度为dp[j] + 1的最长递增子序列，则counts[i] = counts[j](以nums[i]结尾的递增子序列的组合方式就 等于nums[j]结尾的组合方式) 如果lengths[j] + 1 == lengths[i]，说明这个长度的递增子序列已经找到过一次，就更新counts[i],counts[i] += counts[j] (现在的组合方式 + counts[j]的组合方式，即为总的组合方式个数) 初始化： lengths[:] = 1 counts[:] = 1 输出： lengths数组最大值的相应的counts的个数之和

代码：

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: #动态规划 n = len(nums) if n <= 1:return n lengths = [1] * n #lengths[i],以nums[i]结尾的最长递增子序列长度 counts = [1] * n # count[i],以nums[i]结尾的最长递增子序列的组合数量 max_ = 0 for i in range(1,n): for j in range(0,i): if nums[j] < nums[i]: if lengths[j] + 1 > lengths[i]: lengths[i] = max(lengths[i],lengths[j] + 1) counts[i] = counts[j] elif lengths[j] + 1 == lengths[i]: counts[i] += counts[j] max_ = max(max_,lengths[i]) res = 0 for i in range(n): if lengths[i] == max_: res += counts[i] return res

3、复杂度分析：

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