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

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

野性酷女 2022-06-03 07:39 269阅读 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 696. Count Binary Substrings 连续出现相同次数0或1子串数量 + 很棒的做法和 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;
    }
};