一个数串最长子序列一共有多少个（严格递增），DP，dp记录截止第i个数的最长子序列长度，nt记录截止i的最长子序列个数
#673
#Runtime: 1392 ms (Beats 5.5%)
#Memory: 13.6 MB (Beats 77.78%)
class Solution(object):
def findNumberOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
dp = [0] * n
dp[0] = 1
nt = [0] * n
nt[0] = 1
ll = 1
for i in range(1, len(nums)):
mx = 0
fq = 1
for j in range(i):
if nums[j] < nums[i]:
if dp[j] > mx:
mx = dp[j]
fq = nt[j]
elif dp[j] == mx:
fq += nt[j]
nt[i] = fq
dp[i] = mx + 1
if ll < dp[i]:
ll = dp[i]
ans = 0
for i in range(len(dp)):
if dp[i] == ll:
ans += nt[i]
return ans