【子序列】673. 最长递增子序列的个数

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。

解题思路：动态规划

(1) 定义dp数组
maxLenDp[i]：以nums[i]结尾，nums[0:i]中最长递增子序列的【长度】
countDp[i]：以nums[i]结尾，nums[0:i]中最长递增子序列的【个数】

(2) 状态转移方程
现在求解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）：
 当maxLenDp[i] < maxLenDp[j] + 1时，说明要更新：
  ● maxLenDp[i] = maxLenDp[j] + 1
  ● countDp[i] = countDp[j]
 当maxLenDp[i] == maxLenDp[j] + 1时，说明要更新（但仅更新countDp即可）：
  ● countDp[i] += countDp[j]

(3) 初始化
无

(4) 遍历顺序
从左到右

(5) 举例：略

最后，求出来的两个dp数组是分别以 nums[0:i] 子数组结尾的【最大递增子序列长度】【最大递增子序列个数】
需要再次遍历，获得最后的结果（更新最大的递增子序列长度，累加最大递增子序列个数）！

class Solution {
    public int findNumberOfLIS(int[] nums) {
        // dp[i]：以nums[i]结尾，nums[0:i]中最长递增子序列的个数
        int countDp[] = new int[nums.length];
        // dp[i]：以nums[i]结尾，nums[0:i]中最长递增子序列的长度
        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--){
                    // 可以和前面的子序列构成新的最长子序列
                    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];
                    }
                }
                // 不可以和前面的子序列构成新的最长子序列
                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;
    }
}