[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

• 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.