一個數串最長子序列一共有多少個（嚴格遞增），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