I. Topic Description:

Ii. Thinking analysis:

This is a very simple dynamic programming, and here is the general idea of dynamic programming

The dynamic programming algorithm can solve problems with the following characteristics:

  1. Have the same subproblem: First we have to make sure that the problem can be broken down into several subproblems, and that we can solve the problem through these subproblems
  2. Satisfy the principle of optimization (optimal substructure) : the optimal solution of a problem contains the optimal solution of a subproblem. In other words, we can derive the optimal solution of the problem from the optimal solution of the subproblem.
  3. There is no aftereffect: decisions made on each subproblem cannot affect the solution of other future problems which will be explained in a moment how to eliminate aftereffect

The problem solving steps

Step 1: Determine the subproblems of the problem. Key points: Pay attention to analyze which quantities will become smaller as the size of the problem becomes smaller, and which variables are independent of the problem.

The second step: determine the state, key points: combined with sub-problems, dare to think dare to try, do not easily negate a state, more thinking, do not hope that each topic can be accomplished at one move!

Step 3: Introduce the state transition equation: pay attention to verify whether the applicable conditions are met, pay attention not to miss the conditions.

Step 4: Determine boundary conditions Point: First determine according to the meaning of the state, and then verify whether the first layer is correct. If it is not correct or cannot be determined according to the meaning, then the boundary can also be determined by using the value of the first layer.

The fifth step: determine the realization of the key points: according to the topology order is obvious and personal habits to determine!

Step 6: Determine optimization methods if necessary! Key points: pay attention to the priority of dimensionality reduction, do not be limited to monotonous queues, quadrilateral inequalities and other standard things for 譤 to discuss optimization, broaden the thinking, avoid stereotypes!

True knowledge comes from practice

Step 1: In this case, the size of the problem is undoubtedly the maximum length of the array (you can think of it as the right pointer), and as the maximum length decreases, so does the length of the incrementing subsequence. But! The length may also be constant, because the number excluded when the maximum length is reduced is not necessarily included in the current longest increasing subsequence.

The second step: As for the aftereffect problem, it is obvious that whether the ith point is selected as part of the increasing subsequence must have an impact on the subsequent answer, so we set the state as dp[I][0] is the length of I, the ith point is not selected to add the length of the increasing subsequence, dp[I][1] is the length of I, Select the ith point to add the length of the increasing subsequence.

Step 3: Deduce the state transition equation. When the i-th point is not selected to add the increasing subsequence, the maximum length is equivalent to the maximum value of DP [i-1][*]; when the i-th point is selected to add the increasing subsequence, the maximum length is equivalent to a dp[past point]+1, and the value of this point must be strictly smaller than the i-th point. Of course, if no dot satisfies the requirement, set it to 1. Specific as follows

dp[i][0] = max(dp[i - 1] [0] , dp[i - 1] [1]);
dp[i][1] = 1;
if(nums[j] < nums[i])dp[i][1] = max(dp[j][1] + 1, dp[i][1]);
Copy the code

Step 4: boundary conditions. The equation needs to get the answer according to the previous node. Therefore, when I == 0, the step has the previous node, which needs to be specified separately

Step 5: The implementation method is omitted

Step 6: Optimization is omitted

Iii. AC code:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int dp[nums.size()] [2];
        dp[0] [0] = 0;
        dp[0] [1] = 1;
        for(int i = 1 ; i < nums.size(a); i++){ dp[i][0] = max(dp[i - 1] [0], dp[i - 1] [1]);
            int j = i - 1;
            dp[i][1] = 1;
            while(j >= 0) {if(nums[j] < nums[i])dp[i][1] = max(dp[j][1] + 1, dp[i][1]);
                j--;
            }
            // printf("%d:%d ", dp[i][0],dp[i][1]);
        }

        return max(dp[nums.size() - 1] [0] , dp[nums.size() - 1] [1]); }};Copy the code

Iv. Summary:

This problem is not difficult at the same time, the need to eliminate their own effects, I think there is as an example of the value of talking. I’m going to look at dynamic programming again, and I’ll continue this series when I’m done.

This article is participating in the “Nuggets 2021 Spring Recruiting activity”, click to see the details of the activity