給定一個(gè)未排序的整數(shù)數(shù)組 nums ， 返回最長(zhǎng)遞增子序列的個(gè)數(shù) 。
注意 這個(gè)數(shù)列必須是 嚴(yán)格 遞增的。

解題思路：動(dòng)態(tài)規(guī)劃

(1) 定義dp數(shù)組
maxLenDp[i]：以nums[i]結(jié)尾，nums[0:i]中最長(zhǎng)遞增子序列的【長(zhǎng)度】
countDp[i]：以nums[i]結(jié)尾，nums[0:i]中最長(zhǎng)遞增子序列的【個(gè)數(shù)】

(2) 狀態(tài)轉(zhuǎn)移方程
現(xiàn)在求解maxLenDp[i]、countDp[i]，需要遍歷 j（0 ≤ j < i）：
● 如果 i == 0 或者 不存在nums[j] < nums[i]（0 ≤ j < i）：
?● maxLenDp[i] = 1
?● countDp[i] = 1
● nums[j] < nums[i]（0 ≤ j < i）：
?當(dāng)maxLenDp[i] < maxLenDp[j] + 1時(shí)，說(shuō)明要更新：
??● maxLenDp[i] = maxLenDp[j] + 1
??● countDp[i] = countDp[j]
?當(dāng)maxLenDp[i] == maxLenDp[j] + 1時(shí)，說(shuō)明要更新（但僅更新countDp即可）：
??● countDp[i] += countDp[j]

(3) 初始化
無(wú)

(4) 遍歷順序
從左到右

(5) 舉例：略

最后，求出來(lái)的兩個(gè)dp數(shù)組是分別以 nums[0:i] 子數(shù)組結(jié)尾的【最大遞增子序列長(zhǎng)度】【最大遞增子序列個(gè)數(shù)】
需要再次遍歷，獲得最后的結(jié)果（更新最大的遞增子序列長(zhǎng)度，累加最大遞增子序列個(gè)數(shù)）！

class Solution {
    public int findNumberOfLIS(int[] nums) {
        // dp[i]：以nums[i]結(jié)尾，nums[0:i]中最長(zhǎng)遞增子序列的個(gè)數(shù)
        int countDp[] = new int[nums.length];
        // dp[i]：以nums[i]結(jié)尾，nums[0:i]中最長(zhǎng)遞增子序列的長(zhǎng)度
        int maxLenDp[] = new int[nums.length];
        for(int i=0; i<nums.length; i++){
            if(i == 0){
                maxLenDp[i] = 1;
                countDp[i] = 1;
            }else{
                int curLen = 1;
                for(int j=i-1; j>=0; j--){
                    // 可以和前面的子序列構(gòu)成新的最長(zhǎng)子序列
                    if(nums[i] > nums[j]){
                        curLen = maxLenDp[j] + 1;
                        if(curLen > maxLenDp[i]){
                            maxLenDp[i] = curLen;
                            countDp[i] = countDp[j];
                        }else if(curLen == maxLenDp[i]) countDp[i] += countDp[j];
                    }
                }
                // 不可以和前面的子序列構(gòu)成新的最長(zhǎng)子序列
                if(curLen == 1){
                    maxLenDp[i] = 1;
                    countDp[i] = 1;
                }
            }
        }
        int count = 0;
        int maxLen = 0;
        for(int i=0; i<nums.length; i++){
            if(maxLenDp[i] > maxLen){
                maxLen = maxLenDp[i];
                count = countDp[i];
            }else if(maxLenDp[i] == maxLen) count += countDp[i];
        }
        return count;
    }
}