I. Title Description:

Ii. Analysis of Ideas:

Dynamic programming is explained here

Step 1: We have done a simplified version of this problem before, but this time we need to find the number of maximal sequences, so in addition to the length of the maximal sequence dp[k], we also need to maintain the number of maximal sequences s[k].

The second step: Certain state, are using a two-dimensional array is the eldest son sequence is decomposed into the tail is the eldest son of the current node sequence and tail sequence of other nodes of the eldest son because it don’t need to traverse again in return, subject due to the statistics in the length, in order to reduce the complicated degree, change the state representation to dp [k] : the tail is the eldest son of the current node sequence, S [k]: Tail is the maximum number of sequences of the current node.

Step 3: state transition equation. As mentioned earlier, the state transition equation of S [k] is

s[k] += s[j] ;// If dp[k] == dp[j] + 1 and nums[k] > nums[j]
s[k] = s[j] // Dp [k] > dp[j] + 1 and nums[k] > nums[j]
Copy the code

Step 4: Boundary conditions. The equation needs to get the answer according to the preceding nodes. Therefore, when I == 0, the equation has the preceding nodes and needs to be specified separately

Step 5: Implementation is omitted

Step 6: Optimize

Iii. AC Code:


class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size(a);int* d = new int[n];
        int* s = new int[n];
        for (int i = 0; i < n; ++i)
        {
            d[i] = 1;
            s[i] = 1;
        }

        // Record the maximum length
        int maxRes = 1;
        for (int k = 1; k < n; ++k)
        {
            // cout << "k " << k << " " << nums[k] << endl;
            // The current maximum length
            int currMax = 1;
            // The number of subarrays of the maximum length
            int currSum = 1;
            int num = nums[k];
            for (int i = 0; i < k; ++i)
            {
                if (num > nums[i])
                {
                    if (d[i]+1 > currMax)
                    {
                        currSum = s[i];
                        currMax = d[i]+1;
                    }
                    else if (d[i]+1== currMax) { currSum += s[i]; }}// cout << "i " << i << " " << nums[i] << " currMax " << currMax << " s[k] " << s[k] << endl;
            }
            s[k] = currSum;
            d[k] = currMax;
            printf("dk: %d sk: %d \n",d[k],s[k]);
            maxRes = max(maxRes, d[k]);
        }

        int res = 0;
        for (int i = 0; i < n; ++i)
        {
            // cout << d[i] << " " << s[i] << endl;
            if(d[i] == maxRes) { res += s[i]; }}returnres; }};Copy the code

Iv. Summary:

This problem can be said to be the template variant repeated horizontal jump, from thinking about the implementation of no aftereffect, to ignore the effect of no aftereffect and increase a for cycle to achieve the effect, dynamic planning is also like this, write more think, one is to see more templates of all things are templates, one is not stuck in the template to template.

Something like this is more than a dynamic program

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign