[TOC]

This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

If programmers only satisfy CURD, the 35-year-old crisis will soon arrive. Algorithmic thinking should be the main focus of my university. Today we have started our discussion based on a theory we learned in college — dynamic programming

The theory of

  • Break down a big problem into sub-problems. That is, the transformation goes through layers of refinement and eventually becomes a small problem or a given solution.

  • Without further ado, we have gone straight to Leetcode42 — the problem of rainwater

Topic describes

Given n non-negative integers to represent the height diagram of each column of width 1, calculate how much rain the columns in this order can catch after rain.

Example 1:

Enter: height = [0,1,0,2,1,0,1,3,2,1,2,1,2,1]

Output: 6

Explanation: the height diagram above is represented by the array [0,1,0,2,1,0,1,3,2,1,2,1,1], in which case 6 units of rain can be caught (the blue parts are rain).

Example 2:

Enter: height = [4,2,0,3,2,5]

Output: 9

Tip:

n == height.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
Copy the code

Thought analysis

  • Above is the author’s submission record, which is quite fast and does not take up too much memory. Speed on leetCode currently exceeds 100% for Java programs; The best memory usage was over 98%; So let’s just think about how we’re going to solve this problem

  • Those of you who have studied dynamic programming know that normal dynamic programming has several steps.

Determine the transformation equation

  • Because dynamic programming is breaking up big problems into small problems. If I want to get 100 dollars. Let’s say I only have $1 in face value, so I have to get $99 to get $100. The way we go from 100 to 99 is the way we decompose. And so on and so forth we only need 1 dollar to push 100 dollars. There is a difference between this process and recursion. We won’t go into details today.

  • In the problem of receiving rain water, our current amount of receiving water is affected by the post behind.

  • For the convenience of subsequent demonstration, we agree on the following title

Referred to as” meaning
Zn The number of columns; These are the coordinates in the diagram
Sn Represents the capacity of the pool formed as a whole by the NTH pillar
SDn Represents the current water flow in the vertical direction of the NTH pillar
Zmax Represents the height of the highest column to date
Sm,n Represents the pool formed by columns m to N

  • Just like in the problem, when we get to block 6, Z6=0, which means that the pool formed by the column in block 6 is 0. But when the seventh block is with the sixth and fifth block will form a pool.

  • So let’s say that Fx represents the capacity of the pool from 1 to column X.

Determine the initial value

  • The initial value of this problem is not a lot of thought. The first piece is obviously 0, so S0 is 0

Count them from smallest to largest

  • The first step is a flat building. S0=0

  • For the first step, we will start directly from the second pillar, at this time there is no pool without the highest pillar. We calculate S2=0;

  • Then we move the pointer to the third pillar, Z3=0 we understand as flat ground, flat ground does not form a pool. So the S3 = S2 = 0;

  • Next, we go to the fourth pillar, Z4=2, the highest pillar is currently Z2=1; Note that the Z4 has not yet entered the competition for the tallest pillar. So Zmax = Z2 = 1. So let’s follow our formula. There is no column not lower than Z4 in [Z2~Z4], so S4=S2+S4,2

  • S4,2 represents the pool capacity formed from the second to the fourth block S4,2=(4-2-1)*min(Z2,Z4)- column capacity =1

  • So S4 = 0 + 1 = 1;

  • Now the pointer goes to the fifth pillar, there is no space between the fifth and the fourth pillar, so S5=S4=1;

  • On the third pillar we theorized that a pool could not have formed on flat ground. So the sixth column here is just ignored.

  • S6=S5=1

  • Currently the tallest pillar is Z4. Z5 is no less than Z7 in Z4~Z7. So the S7 = S5 and S7, a five

  • S7,5 means the pool from the fifth to the seventh is equal to 1

  • S7=1+1=2.

  • Z8 = 3. In Zmax~Z8 there is no not less than Z8. So it forms a pool directly with Zmax.

  • The S8 = S4 + S8, 4

  • The S8, 4 = min (8-4-1) * (Zmax, Z8) - the sum (Z7 Zmax + 1) = 3 * 2 - (1 + 1) = 6-2 = 4

  • S8=1+4=5

  • There is no gap between the eighth and ninth roots, so there is no pool.
  • S9=S8=5

  • The S10 and S9 have no gaps, so there is no pool
  • S10=S9=6

  • On the 11th pillar, we have Zmax=Z8. We find Z9 not less than Z11. So the S11 = S8 + S11, 9 = 5 + 1 = 6

  • So the final answer is 6.

  • Here I’ve animated the whole process. I think you get the idea of dynamic programming.

  • Let’s look directly at the code implementation.

AC code

  • For the reader to demonstrate the effect. The following procedure is the complete code. Just copy the past import package and run it directly.

public int trap(int[] height) {
    if (height.length == 0) {
        return 0;
    }
    int[] result = new int[height.length];
    int heighMaxIndex = 0;
    for (int i = 1; i < height.length; i++) {
        if (height[i] == 0) {
            result[i] = result[i - 1];
            continue;
        }
        int secondMaxIndex = i-1;
        boolean flag = false;
        for (int j = i - 1; j >= heighMaxIndex; j--) {
            if (height[j] >= height[i]) {
                / / by the column
                int x =i-j-1;
                int y = getHeightCrossX(height,j,i);
                result[i] = result[j] + x * height[i] - y;
                flag=true;
                break;
            }
            if(height[j] > height[secondMaxIndex]) { secondMaxIndex = j; }}if (flag) {
            continue;
        }
        int y = getHeightCrossX(height, secondMaxIndex, i);
        result[i]=result[secondMaxIndex]+height[secondMaxIndex]*(i-secondMaxIndex-1)-y;
        if(height[heighMaxIndex] < height[i]) { heighMaxIndex=i; }}return result[result.length-1];
}

private int getHeightCrossX(int[] height,int j, int i) {
    int y = 0;
    for (int k = j + 1; k < i; k++) {
        y += height[k];
    }
    return y;
}

public static void main(String[] args) {

    LeetCode42 leetCode = new LeetCode42();
    System.out.println(leetCode.trap(new int[] {0.1.0.2.1.0.1.3.2.1.2.1}));

}


Copy the code

conclusion

  • The rainwater problem is a typical dynamic programming problem, but its first step will be affected by the next steps. So we need to find a formula that doesn’t affect the previous step. That’s the highest bar that we push to the middle scale. Because the tallest column is formed as a wall, the left side of the wall is protected.