leetcode 673. Number of Longest Increasing Subsequence LISS最长递增子序列数量+动态规划

野性酷女 2022-06-03 07:39 170阅读 0赞

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.  
Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

本题基本上和之前的是一样的做法

dp\[i\]定义为以nums\[i\]为结尾的递推序列的个数的话，再配上这些递推序列的长度，将会比较容易的发现递推关系。这里我们用len\[i\]表示以nums\[i\]为结尾的递推序列的长度，用cnt\[i\]表示以nums\[i\]为结尾的递推序列的个数，初始化都赋值为1，只要有数字，那么至少都是1。然后我们遍历数组，对于每个遍历到的数字nums\[i\]，我们再遍历其之前的所有数字nums\[j\]，当nums\[i\]小于等于nums\[j\]时，不做任何处理，因为不是递增序列。反之，则判断len\[i\]和len\[j\]的关系，如果len\[i\]等于len\[j\] + 1，说明nums\[i\]这个数字可以加在以nums\[j\]结尾的递增序列后面，并且以nums\[j\]结尾的递增序列个数可以直接加到以nums\[i\]结尾的递增序列个数上。如果len\[i\]小于len\[j\] + 1，说明我们找到了一条长度更长的递增序列，那么我们此时奖len\[i\]更新为len\[j\]+1，并且原本的递增序列都不能用了，直接用cnt\[j\]来代替。我们在更新完len\[i\]和cnt\[i\]之后，要更新mx和res，如果mx等于len\[i\]，则把cnt\[i\]加到res之上；如果mx小于len\[i\]，则更新mx为len\[i\]，更新结果res为cnt\[i\]

建议和[leetcode 300. Longest Increasing Subsequence 最长递增子序列LISS][leetcode 300. Longest Increasing Subsequence _LISS] 一起学习

建议和[leetcode 696. Count Binary Substrings 连续出现相同次数0或1子串数量 + 很棒的做法][leetcode 696. Count Binary Substrings _0_1_ _] 和 [leetcode 467. Unique Substrings in Wraparound String 连续字符串长度统计+动态规划DP][leetcode 467. Unique Substrings in Wraparound String _DP]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution
    {
    public:
        int findNumberOfLIS(vector<int>& nums) 
        {
            vector<int> dp(nums.size(), 1);
            vector<int> count(nums.size(), 1);
            int maxLen = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                for (int j = 0; j < i; j++)
                {
                    if (nums[j] < nums[i])
                    {
                        if (dp[i] == dp[j] + 1)
                            count[i] += count[j];
                        else if (dp[i] < dp[j] + 1)
                        {
                            dp[i] = dp[j] + 1;
                            count[i] = count[j];
                        }
                    }   
                }
                maxLen = max(maxLen, dp[i]);
            }
    
            int res = 0;
            for (int i = 0; i < nums.size(); i++)
            {
                if (maxLen == dp[i])
                    res += count[i];
            }
            return res;
        }
    };

[leetcode 300. Longest Increasing Subsequence _LISS]: http://blog.csdn.net/jackzhang_123/article/details/78122446
[leetcode 696. Count Binary Substrings _0_1_ _]: http://blog.csdn.net/jackzhang_123/article/details/78881335
[leetcode 467. Unique Substrings in Wraparound String _DP]: http://blog.csdn.net/jackzhang_123/article/details/78810212