Algorithm interview Replay: Triangle minimum path sum (bytes)

In the last article, we studied the analysis methods of DP (dynamic programming) in online relationships by using the topics “Longest ascending subsequence” and “maximum suborder sum”. This analysis method is also known as “linear dynamic programming” in operations research, which specifically refers to “linear functions with specific variables as the objective function, linear inequalities or equations of these variables as constraints, and the purpose is to find the maximum or minimum value of the objective function”. This point as we can understand, do not need to remember, not to copy!

In this section, we will continue to analyze a slightly different from the previous topic type, hope to be able to compare this topic with the previous topic demonstration, and then smooth solution!

01. Topic analysis

For example, given a triangle:

[[2], [3,4], [6,5,7], [4,1,8,3]Copy the code

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

This problem has certain difficulty oh! If you do not have ideas, please review the last learning content!

It is not recommended to read the problem directly!

02. Title Diagram

So first of all, we’re going to look for the sum of minimum paths of a triangle, what does that mean? Suppose we have a triangle: [[2], [3,4], [6,5,7],

,1,8,3 [4]]

So the minimum sum of paths from top to bottom is 2-3-5-1, which is 11.

Since we are using an array to define a triangle for our analysis, we change the triangle slightly:

So we’re stretching the whole triangle. In this case, according to the conditions given in the problem: each step can only move to the next row adjacent

At the node of. This is essentially the same thing as saying, for every step we can only move one down or one down to the right. Convert it to code, let’s say 2 is in the element

If the prime position is [0,0], then we can only move down to [1,0] or [1,1]. If 5 is in position [2,1], it can also move

To the positions [3,1] and [3,2]. As shown below:

Now that the problem is clear, let’s start the analysis. The problem is obviously a problem of finding the optimal solution, and can be derived from the optimal solution of the subproblem

Line build. So we solve it by dynamic programming. First, we define the state:

Dp [I][j] : represents the minimum path sum of elements containing the ith row and j column

It’s easy to think of top-down analysis. And, whatever the final path is, it must go through the topmost element, which is [0,0]. So we need to initialize dp[0][0].

Dp [0][0] = the value of the element at position [0]

Further analysis, if we ask dp[I][j], then it must move from the two elements above its head.

The minimum path sum at 5, for example, is either 2-3-5 or 2-4-5. Then take the smaller of the sum of the two paths. Into the

And we get the state transition equation:

dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]

However, we have a problem here! Except for the element at the top,

The element on the left can only come from above. (2-3-6-4)

The rightmost element can only come from its upper left corner. (2-4-7-3)

Then, we observe that the elements in line 2 are special elements (because they can only come from the element [0,0])

We can directly treat it specially and get:

dp[1][0] = triangle[1][0] + triangle[0][0]
dp[1][1] = triangle[1][1] + triangle[0][0]

In the end, we just have to find the smallest path sum in the last row, and that’s our answer. That is:

L: dp array length
Result = min(dp[l-1,0], dp[l-1,1], dp[l-1,1]….)

To sum up, we have finished the analysis. We have carried out 4 steps in total:

1. Define state
2. Summarize the state transition equation
3. Analyze the special case where the state transition equation cannot be satisfied.
4. Get the final solution

03. Examples of Go language

According to the above analysis, the code can be obtained as follows:

func minimumTotal(triangle [][]int) int {
    if len(triangle) < 1 {
        return 0
    }
    if len(triangle) == 1 {
        return triangle[0] [0]
    }
	dp := make([] []int.len(triangle))
	for i, arr := range triangle {
		dp[i] = make([]int.len(arr))
	}
    result := 1<<31 - 1
	dp[0] [0] = triangle[0] [0]
	dp[1] [1] = triangle[1] [1] + triangle[0] [0]
	dp[1] [0] = triangle[1] [0] + triangle[0] [0]

	for i := 2; i < len(triangle); i++ {
		for j := 0; j < len(triangle[i]); j++ {
			if j == 0 {
				dp[i][j] = dp[i- 1][j] + triangle[i][j]
			} else if j == (len(triangle[i]) - 1) {
				dp[i][j] = dp[i- 1][j- 1] + triangle[i][j]
			} else {
				dp[i][j] = min(dp[i- 1][j- 1], dp[i- 1][j]) + triangle[i][j]
			}
		}  
	}
    for _,k := range dp[len(dp)- 1] {
        result = min(result, k)
    }
	return result
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
Copy the code

Running results:

Running the above code, we find that we are using too much memory. Is there any way we can compress memory? Through observation we find that in our

In the top-down process, we only need to use the accumulated data in the previous layer, and do not revisit the previous number of elements

According to. The graph is as follows:

The optimized code looks like this:

func minimumTotal(triangle [][]int) int {
    l := len(triangle)
    if l < 1 {
        return 0
    }
    if l == 1 {
        return triangle[0] [0]
    }
    result := 1<<31 - 1
	triangle[0] [0] = triangle[0] [0]
	triangle[1] [1] = triangle[1] [1] + triangle[0] [0]
	triangle[1] [0] = triangle[1] [0] + triangle[0] [0]
	for i := 2; i < l; i++ {
		for j := 0; j < len(triangle[i]); j++ {
			if j == 0 {
				triangle[i][j] = triangle[i- 1][j] + triangle[i][j]
			} else if j == (len(triangle[i]) - 1) {
				triangle[i][j] = triangle[i- 1][j- 1] + triangle[i][j]
			} else {
				triangle[i][j] = min(triangle[i- 1][j- 1], triangle[i- 1][j]) + triangle[i][j]
			}
		}  
	}
    for _,k := range triangle[l- 1] {
        result = min(result, k)
    }
	return result
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
Copy the code

Running results:

I’ve compiled all the problems I’ve written into an e-book, complete with illustrations for each problem. Click to download