Number of Longest Increasing Subsequence

Given an unsorted array of integers, find the number of longest increasing subsequence.
Example 1:
Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

這題挺難的，看到LIS自然想到DP，但這題是二維DP，除了常規(guī)的len[]來記錄end with當(dāng)前數(shù)字的LIS長度，還需要一個維度cnt[]記錄end with當(dāng)前數(shù)字（必須包含當(dāng)前數(shù)字，比如1,2,4,3, cnt[3]是1而不是2）的LIS個數(shù)。

注意，這些DP都是強(qiáng)調(diào)一個end with，也就是「必須包含當(dāng)前數(shù)字」。
因?yàn)楸容^的過程中都是拿當(dāng)前數(shù)字跟前面的數(shù)字比，且若當(dāng)前數(shù)字不比前面的數(shù)字大，len[i]將一直維持在1。

最后，LIS的轉(zhuǎn)移方程不要記反了（我一開始記成len[i] + 1了，是錯的）: if (len[i] < len[j] + 1) {len[i] = len[j] + 1;}

    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, res = 0, max_len = 0;
        int[] len = new int[n], cnt = new int[n];
        for (int i = 0; i < n; i++) {
            len[i] = cnt[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    if (len[i] == len[j] + 1)
                        cnt[i] += cnt[j];
                    if (len[i] < len[j] + 1) {
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    }
                }
            }
            if (max_len < len[i]) {
                max_len = len[i];
            }
        }
                //所有的長度等于max_len的cnt，加起來
        for (int i = 0; i < nums.length; i++) {
            if (len[i] == max_len) {
                res += cnt[i];
            }
        }
        return res;
    }