【LeetCode】673. 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），一个经典的动态规划问题)。其实就是LIS的变体。 摘自九章算法

1. 设dp[i]为以该数结尾，能构成的最长序列的长度。进行连接的时候，对于每个数字num[i]，遍历位置在它之前的数字num[j]，如果比这个数小（num[j]<num[i]），也就是能构成一个序列，这样就能进行状态转移，我们令dp[i]=max(dp[i],dp[j]+1)来保证存储的为最长长度，同时可以记录max(dp[i])

2. 考虑完题目的长度优先后，我们考虑数量，也就是说最长长度的序列有几个，这个问题需要我们在处理dp的时候来记录，我们设ans[i]为以第i个数结尾的最长序列的个数，与dp同理，ans初值也都是1

 3. 状态转移的时候，如果dp更新了，也就是说（dp[j]+1>dp[i]）说明这个长度的序列是新出现的，我们需要将ans[i]设置为ans[j]，因为新序列中，最新的数提供了序列的尾巴，数量是由前面积累的（或者说转移）；举例序列[1 1 3 7]我们易得数字3对应的dp=2,ans=2,因为可以构成两个[1 3]那么我们操作到数字7的时候，发现接在3后面最长，就可以转移ans来作为初始数量

 4. 而当dp[j]+1==dp[i]的时候，如同样例，操作7的时候，我们最先发现了可以接在5后面，最长序列[1 3 5 7],然后发现可以接在4后面，[1 3 4 7]，长度也是4，这时候就同样需要转移ans，加上去 ans[i]+=ans[j]

 5. 最后我们需要遍历dp，找到dp[i]=我们记录的最大值的时候，累加我们得到的ans[i]，即为所求结果，时间复杂度是O(n^2)

Solution 

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size(), max_len = 1, res = 0;
        vector<int> dp(n, 1), cnt(n, 1);
        for(int i = 1; i < n; ++i){
            for(int j = 0; j < i; ++j){
                if(nums[j] < nums[i] && dp[j] + 1 > dp[i]){
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j];
                } else if(nums[j] < nums[i] && dp[j] + 1 == dp[i]){
                    cnt[i] += cnt[j];
                }
            }
            max_len = max(max_len, dp[i]);
        }
        for(int i = 0; i < n; ++i)
            if(dp[i] == max_len) res += cnt[i];
        return res;
    }
};