Cut to the chase

Straight to the point:

Let’s say I have a triangletriangleFind the minimum path from the vertex to the bottom.

Note: each move can only go down, and each move can only go to adjacent nodes.

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]

Output: 11

Explanation: As shown in the schematic diagram below:

The minimum sum of paths from top to bottom is 11 (that is, 2 + 3 + 5 + 1 = 11).

Analysis of the problem

Since it is a deliberate exercise of dynamic programming, this topic is of course to use dynamic programming to answer. So let’s first analyze why dynamic programming comes to mind when we see this problem. Mainly because this topic has the following characteristics:

1. Each move is related to the last one. For example, when you reach the node with the value of 3 in the example, you can only move to 6 or 5 in the next step

2. They’re asking us not to list every step, but to find a minimum.

In accordance with the above two points, the first method we should consider is dynamic programming, since the choice of dynamic programming we focus on finding the law (dynamic transfer equation), and finding the initial value (boundary conditions)

Step 1: We define a result array. If we want to record the minimum value on each node, our result array needs to be consistent with the array of parameters to properly record the minimum value on each node.

Therefore, we can easily conclude that we need to create a new two-dimensional array to store the value:

Const dep = triangle. Length const result = new Array(dep); for (let i = 0; i < dep; i++) { result[i] = new Array(triangle[i].length); }Copy the code

Step 2: We find the initial value, and the initial value is usually the first node. In our example, our first initial value is the sum of the first value at the 0th level of result

 result[0][0] = triangle[0][0]
Copy the code

The third step is to find a pattern:

Find rules like our novice player proficiency is not very enough of the case, we must not be anxious ~ suddenly find out the rules we can start from the second layer. For example, when the second layer reaches 3 and 4 nodes, we can easily calculate the sum value of the corresponding point in result. At the point 3, added from the first layer, the sum is 2+3=5, and 4+2=6.

/ / node 3 result [1] [0] = result [0] [0] + triangle [0, 0] / / node 4 result [1] [1] = result [0] [0] + triangle [0, 0]Copy the code

If the problem is finished at this point and we need to find the smallest path, we simply return math.min (result[1][0],result[1][1]).

Similarly, at the third layer, we can use this method to calculate the sum of nodes 6 and 7, but the key is the node with the value of 5. The value of 5 can come from either node 3 or node 4. So what determines which node we sum from? Is it also the smallest of the two?

From this we can conclude:

/ / node 5 minimum result of [2] [1] = math.h min (result [1] [1], the result [1] [0]) + triangle (2, 1]Copy the code

To sum up, we try to summarize the law, and we can get the following three points:

1. The first column of a row can only be added from the first column of the previous row

2. The last line can only be added from the last line in the previous row

3. The minimum sum of the middle part of each row is the minimum sum of the points that can be reached in the previous row

Step 4: Translate the rules into codes. We use the first loop to cycle the number of layers, subscript I, and the second loop to cycle the nodes. The table below is J, so the three rules summarized above can be translated into the following code:

Rule 1: the result [I] [0] = result [0] + [I – 1] triangle [I] [0]

Rule 2:

for (let j = 1; j < i; j++) {
            result[i][j] = Math.min(result[i - 1][j], result[i - 1][j - 1]) + triangle[i][j]
        }
Copy the code

Result [I][I] = result[i-1][i-1] + triangle[I][I]

Finally we get result, just return the minimum value in the last layer math.min (… Result [result.length-1]) is the result we want!

Overall code:

Var minimumTotal = function (triangle) {const dep = triangle. Length const result = new Array(dep); for (let i = 0; i < dep; i++) { result[i] = new Array(triangle[i].length); } result[0][0] = triangle[0][0] for (let i = 1; i < dep; Result [I][0] = result[I - 1][0] + triangle[I][0] for (let j = 1; j < i; J++) {result [I] [j] = math.h min (result [j], [I - 1] result [I - 1] [1]) + triangle [I] [j]} / / f [I] [I] is the ith row last one, Result [I][I] = result[I - 1][I - 1] + triangle[I][I][I]} Return math.min (... result[result.length - 1]) }; MinimumTotal ([[2], [3, 4], [6, 5, 7], [4,1,8,3]])Copy the code

The above is the 70 decomposition method of this topic (because the spatial complexity of this solution is a little high), I think the third and fourth steps of dynamic planning are the heavy and difficult points of dynamic planning. How to overcome this difficult point, I think the only way to do under the premise that IQ will not change suddenly is a lot of deliberate practice. (For 100 percent solution, please go here.)

Whisper BB link

One was set up on WednesdayflagI said I was going to finish the book deliberate Practice on Saturday and write a few impressions and a classic dynamic programming problem solution. In general, I was halfway there (because I hadn’t finished the book)

Before reading “Danshari” this book, found that this kind of books have a characteristic – the whole book is to tell you the title. Use different perspectives and examples from the first to the last chapter to hammer this idea into your head. This makes for a poor reading experience. It’s kind of like you read chapter 1 and chapter 2 and you kind of know what the rest of the chapters are going to be about, maybe with a different person’s story.

Deliberate Practice expresses a different point of view about the 10,000-hour rule. It thinks that to become a leader in an industry or to cultivate a skill to the level of a master, the 10,000-hour rule is a little general. What is important is deliberate practice out of the comfort zone. Examples of absolute pitch and rapid memorization of numbers are good examples of the power and importance of deliberate practice. Just give me one more week and I will finish reading this book. Then I will talk to you in the next article

One more thing TO share: I’ve found a great way to get up early. Get a ride the day before and pay in advance to give yourself an early reason to get up four days in a row! There are two advantages to doing this:

1. Waking up early frees up a whole chunk of time in the morning, which is great for algorithms and ideas!

2. Hitchhiker owners have stories and it’s really fun to talk to them!

3. There’s really a difference between waking up early and waking up late. As long as you go to bed before midnight!

Finally, if you see this, please give me a like or leave a comment or correction

I’ll probably start brushing next timeThe sliding windowThis elitist freak