This article is participating in the “Java Theme Month – Java brush questions clock”, see < activity links > for more details.

【Java brush questions punch card 】 Brushing questions is much better than playing games, and the sense of achievement is getting stronger and stronger. I insist on brushing several questions every day, exercising for 30 minutes every day, waiting for 8-block abs and waiting for offers from big factories.

Then do it! This column is all about dynamic planning, I will start from the shallow to the deep, step by step, brush questions is such a need for continuous memory – Ebbinghaus memory method 2121112. There isn’t much about dynamic programming, but it’s a must for every programmer


This is a classic 😄😄😄 \color{green}{😄 😄 😄 ~}

What problem can I choose to do dynamic programming?

Counting 1.

  • How many ways can I get to the bottom right corner
  • How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

  • The maximum numeric sum of the path from the upper left corner to the lower right corner
  • Maximum ascending subsequence length

3. Seek existence

  • Stone game, whether the first hand will win
  • Can we pick k numbers such that the sum is sum

Leecode 120. Triangle minimum path sum

Given a triangle triangle, find the minimum sum of paths from the top down.

Each step can only move to the next node in the next row. Adjacent nodes in this case are two nodes whose subscripts are the same or equal to the subscripts of the nodes at the previous level + 1. That is, if subscript I is right on the current row, then the next subscript can be moved to I or I + 1 on the next row.

Example 1:

Input: triangle = [[2], [3, 4], [6, 5, 7], [4,1,8,3]] output: 11 explanation: as shown in the diagram below:

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

Triangle = [[-10]] Output: -10

Tip:

1 <= triangle.length <= 200

triangle[0].length == 1

triangle[i].length == triangle[i – 1].length + 1

-104 <= triangle[i][j] <= 104

Advanced:

Can you just use O(n) of the extra space (n is the total number of rows of the triangle) to solve this problem?

—

Four steps for dynamic planning ~~~ ❤️❤️❤️❤️

This problem, too easy

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

The last step

So if we just look at the graph, we can only go to the neighboring nodes, and then the last step must be

I went from i-1 to J-1

J is coming from i-1

subproblems

The subproblem, of course, is to use an array to store the smallest path that you’ve traveled before

A step towards the final step

So we can get

Min (f [I – 1] [j – 1], [I – 1] f [j]) + c [I] [j].

In addition to subtraction, we can also do this by addition.

C is the current value at this position.

Nice \color{yellow}{very nice ~} very nice ❤️❤️❤️

2.2. Dynamic programming component 2: Transfer equation

Nothing to say. If you don’t see it, go back to the link at the beginning of this article and try to read the initial dynamic programming article

F [I] [j] = min (f [I – 1], [j – 1] f [I – 1) [j]) + c [I] [j].

2.3. Dynamic programming component 3: Initial conditions and boundary cases

f[0][0]=c[0][0]

J = I: f[I −1][I −1]+c[I][I]

J = 0: f[I −1][0]+ C [I][0

2.4. Dynamic programming component 4: Order of calculation

The top-down

Reference code

Java version

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        // dp[I][j] represents the minimum sum of paths from point (I, j) to the bottom edge.
        int[][] dp = new int[n + 1][n + 1];
        // Start from the last line of the triangle.
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle.get(i).get(j); }}return dp[0] [0]; }}Copy the code

Isn’t it a little simplistic? Somebody else says On but now it’s On2 time, right? How to optimize?

You start recursing from the last row of the triangle.

Only to the next line of dp [j] [I + 1] dp [j] and [I + 1] dp + 1] [I [m + 1] dp + 1] [I] [j + 1.

Imagine that we represent the minimum path in a row

Is it the time complexity of On?

JAVA version

 
   class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j); }}return dp[0]; }}Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️