动态规划
class Solution:
def findNumberOfLIS(self, nums):
nums.append(float('inf'))
size = len(nums)
dp = [1] * size
cnt = [1] * size
for i in range(size):
for j in range(i):
if nums[i] > nums[j]:
if dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
cnt[i] = cnt[j]
elif dp[i] == dp[j] + 1:
cnt[i] += cnt[j]
return cnt[size - 1]
状态dp[i]表示到i为止递增子序列的最大长度，cnt[i]表示到i为止达到长度dp[i]的序列数
--从0到size遍历i
--从0到i遍历j
--如果i数字大于j数字
--(更新dp[i]为dp[i]和dp[j]+1中的最大值)
--如果dp[i]小，dp[i] = dp[j]+1（到i最大长度为到j最大长度+1）
cnt[i] = cnt[j]（到i最大长度的个数和到j最大长度的个数相等）
--如果二者相等，cnt[i] += cnt[j]（初始值为1，二者相等说明在遇到了相同最大长度的不同子序列，此时到i最大长度的个数要加上到j最大长度的子序列个数）
--返回cnt最后一个元素，即到inf的最长递增子序列个数（加入inf对个数不影响，因为一定大于前面所有数）
举例：
传入[1, 3, 5, 4, 7]
nums = [1, 3, 5, 4, 7, inf], dp = [1, 1, 1, 1, 1, 1], cnt = [1, 1, 1, 1, 1, 1]
当i=4时
dp = [1, 2, 3, 3, 1, 1], cnt = [1, 1, 1, 1, 1, 1], j = [0, 4)
j = 0, nums[4] > nums[0](7 > 1), dp[4] < dp[0] + 1(1 < 1 + 1), dp[4] = 1 + 1, cnt[4] = cnt[0](1->1)
dp = [1, 2, 3, 3, 2, 1], cnt = [1, 1, 1, 1, 1, 1]
j = 1, nums[4] > nums[1](7 > 3), dp[4] < dp[1] + 1(2 < 2 + 1), dp[4] = 2 + 1, cnt[4] = cnt[1](1->1)
dp = [1, 2, 3, 3, 3, 1], cnt = [1, 1, 1, 1, 1, 1]
j = 2, nums[4] > nums[2](7 > 5), dp[4] < dp[2] + 1(3 < 3 + 1), dp[4] = 3 + 1, cnt[4] = cnt[2](1->1)
dp = [1, 2, 3, 3, 4, 1], cnt = [1, 1, 1, 1, 1, 1]
j = 3, nums[4] > nums[3](7 > 4), dp[4] == dp[3] + 1(4 = 3 + 1), cnt[4] += cnt[3](1->2)
dp = [1, 2, 3, 3, 4, 1], cnt = [1, 1, 1, 1, 2, 1]
（太难）
