主題
題目連結：
題目意譯：
給定一個整數(shù)陣列 nums，回傳最長遞增子序列（Longest Increasing Subsequences，LIS）的數(shù)量。
注意到這些序列應為嚴格遞增。
限制：
1 ≦ nums.length ≦ 2000
-10 ^ 6 ≦ nums[i] ≦ 10 ^ 6
範例測資：
範例 1：
輸入： nums = [1,3,5,4,7]
輸出： 2
解釋： 兩個最長遞增子序列為 [1, 3, 4, 7] 和 [1, 3, 5, 7]。
範例 2：
輸入： nums = [2,2,2,2,2]
輸出： 5
解釋： 最長遞增子序列的長度為 1，而裡面有 5 個長度為 1 的最長遞增子序列，所以輸出 5。
解題思維：
雖然是 LIS 的題目，可是這題如果要照著經(jīng)典的 O(n log n) 解法會比較難寫，其中 n 是 nums 的長度。而這題可以回到 O(n ^ 2) 的動態(tài)規(guī)劃（Dynamic Programming，DP）解法。
定義一個一維陣列 D，其中 D[i] 代表著以 nums[i] 作為結尾的 LIS 之長度。其遞迴式為：
D[0] = 1、
D[i] = max(1, D[j] + 1)，其中 0 ≦ j < i 且 nums[j] < nums[i]。
而我們可以額外加上另一個一維陣列 C 在過程中來記錄數(shù)量，其中 C[i] 代表以 nums[i] 作為結尾且長度最長的 LIS 有幾個。而遞迴式為：
C[0] = 1、
C[i] = sum(C[j])，其中 0 ≦ j < i 且 D[j] + 1 == D[i]，而 sum() 代表著把所有元素加總。
最後令 M 為 nums 中 LIS 的長度（現(xiàn)在不限制結尾元素了）。而所求為所有 C[i] 之總和，其中 0 ≦ i < n 且 D[i] == M。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
