步骤一、确定状态:
确定dp数组及下标含义
dp[i]表示以nums[i]结尾的数组最长递增子序列的长度, count数组, count[i]记 录以nums[i]结尾的数组,最长递增子序列的个数。
步骤二、推断状态方程:
dp[i]是与前面的所有状态有关的,所以count[i]也和前面所有状态有关。遍历nums[i]前面的数,如果nums[j]小于nums[i] 了, 这里不能用max更新dp[i]了,而是要加判断
if dp[j] + 1 > dp[i]: dp[i]要更新到最大长度,同时 cout[i]=count[j],也要更新到最大长度的个数
if dp[j] + 1 == dp[i]: 这说明遇到了相同最长长度的子序列,这 时候个数要累加 count[i] += count[j]
步骤三、规定初始条件:
初始条件:
全局初始化都是1,count也是全1初始化,最小个数就是1个 了
步骤四、计算顺序: 外层i从前往后, 内层从0到i
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
# 异常判断
if len(nums) == 1:
return 1
# 初始化
dp = [1] * len(nums)
count = [1] * len(nums)
max_len = 1
# 循环遍历
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
count[i] = count[j]
elif dp[j] + 1 == dp[i]:
count[i] += count[j]
max_len = max(max_len, dp[i])
# 统计个数
res = 0
for i in range(len(nums)):
if dp[i] == max_len:
res += count[i]
return res