題目
難度：★★★☆☆
類型：數(shù)組
方法：動態(tài)規(guī)劃
力扣鏈接請移步本題傳送門
更多力扣中等題的解決方案請移步力扣中等題目錄
給定一個未排序的整數(shù)數(shù)組党饮，找到最長遞增子序列的個數(shù)憎兽。
示例 1:
輸入: [1,3,5,4,7]
輸出: 2
解釋: 有兩個最長遞增子序列蛔琅，分別是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:
輸入: [2,2,2,2,2]
輸出: 5
解釋: 最長遞增子序列的長度是1窘哈，并且存在5個子序列的長度為1，因此輸出5家夺。
注意: 給定的數(shù)組長度不超過 2000 并且結(jié)果一定是32位有符號整數(shù)疤坝。
解答
最長遞增子序列的問題常常使用動態(tài)規(guī)劃來解決∨悖回顧一下如何求最長遞增子序列的長度的問題亲雪。我們準備一個長度為len(nums)的數(shù)組length，其中l(wèi)ength[i]表示以nums[i]為結(jié)尾元素的最長遞增子序列的長度疚膊，初始狀態(tài)填充為1义辕。
需要進行兩次遍歷，外層循環(huán)的下標i從0到len(nums)寓盗，內(nèi)層循環(huán)的下標j從0到i灌砖，這里也就保證了j<i璧函，每當遇到nums[j]<nums[i]時，說明以nums[j]結(jié)尾的遞增子序列（任意一個）有條件將nums[i]吸納進去基显，并壯大自己的力量蘸吓，使本遞增子序列的長度增加1，用代碼來表示也就是length[i] = max(length[i],length[j]+1)撩幽，表達的含義就是以nums[i]結(jié)尾的最長子序列的長度在以nums[j]結(jié)尾的最長子序列的長度的基礎(chǔ)上增加nums[i]這個元素库继。
如果需要統(tǒng)計個數(shù)，我們準備一個新的數(shù)組count窜醉，并初始化為1宪萄，用來記錄以nums[i]結(jié)尾的最長上升子序列的個數(shù)，例如上面描述的每當遇到nums[j]<nums[i]榨惰，更新長度向量的同時還要更新count向量拜英，由于nums[i]相當于以nums[j]結(jié)尾的最長序列的一個向外擴展，因此直接繼承nums[j]結(jié)尾的最長子序列的個數(shù)即可读串，也就是count[i]=count[j]聊记。
但是，只有繼承是遠遠不夠的恢暖，在合適的時候還需要進行更新。這里需要說明一下的是狰右，lenght向量中任意一個位置杰捂，是有可能被更新多次的，如果length[i]處已經(jīng)有值棋蚌，它被覆蓋的條件是有更大的值的出現(xiàn)嫁佳。如果我們得到的length[j]+1正好和這個位置處的值lenght[i]相等說明什么呢？說明的是以nums[i]結(jié)尾的最長上升子序列在本次更新之前已經(jīng)出現(xiàn)過了谷暮，出現(xiàn)的次數(shù)存在count[i]位置處蒿往，為了表達這種出現(xiàn)的重復(fù)，我們將以nums[j]結(jié)尾的最長上升子序列的出現(xiàn)次數(shù)和上一次的出現(xiàn)次數(shù)累加湿弦，并更新到count[i]位置就好了瓤漏，這是這道題的難點。
最終返回的是出現(xiàn)長度最長的子序列出現(xiàn)的次數(shù)颊埃，如果python不熟可以查一下資料理解代碼蔬充。
class Solution(object):
def findNumberOfLIS(self, nums):
N = len(nums)
if N <= 1:
return N
length = [1] * N
count = [1] * N
for i, num in enumerate(nums):
for j in range(i):
if nums[j] < nums[i]:
if length[j] >= length[i]:
length[i] = max(length[i], 1 + length[j])
count[i] = count[j]
elif length[j] + 1 == length[i]:
count[i] += count[j]
longest = max(length)
return sum(c for i, c in enumerate(count) if length[i] == longest)
如有疑問或建議，歡迎評論區(qū)留言~
有關(guān)更多力扣中等題的python解決方案班利，請移步力扣中等題解析
