Dynamic programming advancements – triangle minimum path sum

This is the 20th day of my participation in the Genwen Challenge

$\color{red}{if you are not familiar with dynamic programming, please refer to this chapter ~}$

Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card

$\color{green}{this question is very interesting, do not see regret! 😄 😄 😄 ~}$

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

The language version

func minimumTotal(triangle [][]int) int  {
    n := len(triangle)
    f := make([] []int, n)
    for i := 0; i < n; i++ {
        f[i] = make([]int, n)
    }
    f[0] [0] = triangle[0] [0]
    for i := 1; i < n; i++ {
        f[i][0] = f[i - 1] [0] + triangle[i][0]
        for j := 1; j < i; j++ {
            f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i]
    }
    ans := math.MaxInt32
    for i := 0; i < n; i++ {
        ans = min(ans, f[n- 1][i])
    }
    return ans
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}



Copy the 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?

GO version

func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    f := make([]int, n+1)
    for i := n-1; i >= 0; i-- {
        for j := 0; j <= i; j++ {
            f[j] = min(f[j], f[j + 1]) + triangle[i][j]
        }
    }
    return f[0]}func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

Copy the code

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 very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!

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

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.