最长递增子序列的个数

题目链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/
题目描述：

题解：
题解链接：https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/solution/gong-shui-san-xie-lis-de-fang-an-shu-wen-obuz/

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if(nums.size() < 1)
            return 0;
        int maxLen = 1;
        vector<int> dp( nums.size(), 1); //dp[i]记录i之前（包括i）最长递增序列的长度。
        vector<int> count( nums.size(), 1);//以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]
        for(int i = 1; i < nums.size(); i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(nums[i] > nums[j])
                {
                    if(dp[j] + 1 > dp[i])
                    {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }else if(dp[j] + 1 == dp[i])
                    {
                        count[i] += count[j];
                    }
                }
            }
            maxLen = max(maxLen, dp[i]);
        }
        int maxCount = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(maxLen == dp[i])
                maxCount += count[i];
        }
        return maxCount;
        
    }
};