Algorithm interview Replay: Minimum path and (bytes)

In the last paper, we successfully solved the dynamic programming problem of “triangle minimum path sum” through analysis. In this section, we continue to look at a similar type of problem in order to fully grasp this “path sum” problem. Without further ado, let’s look at the title:

01. Topic analysis

Note: you can only move one step down or right at a time.

Example:

,3,1 input: [[1],,5,1 [1], [4, 2, 1]] output: 7 explanation: because the path 1-3-1-1-1 the sum of the minimum.Copy the code

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

First of all, let’s analyze the problem, and we want to find the minimum sum of paths, what does that mean? Suppose we have an m * n rectangle: [[1,3,1],[1,5,1],[4,2,1]]

So the sum of the smallest paths from the top left to the bottom right, which we can easily see is 1-3-1-1-1, this path, is equal to 7.

Now that the problem is clear, let’s move on. This problem is the same as the previous one to find the minimum path sum of a triangle. The problem obviously fits and can be constructed from the optimal solution of the subproblem, so we consider using dynamic programming to solve it. First, we define the state:

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

Again, because any path to the lower right corner is going to go through the element [0,0]. So we need to initialize dp[0][0].

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

So if we want dp[I][j], it must be coming from above or to the left of itself. As shown below:

5 can only come from 3 or 1 2 can only come from 5 or 4 4 can only come from 1 3 can come from 1
(The red position must move from the blue position)

Then we get the state transition equation:

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

Also, we need to consider two special cases:

• The top line can only be moved from the left (1-3-1)
• Leftmost column, which can only be moved from the top (1-1-4)

Finally, because our goal is to go from the top left to the bottom right, the minimum sum of the entire grid is actually the minimum sum of the paths that contain the elements in the bottom right. That is:

Let: the length of dp be L
Len (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 minPathSum(grid [][]int) int {
	l := len(grid)
	if l < 1 {
		return 0
	}
	dp := make([] []int, l)
	for i, arr := range grid {
		dp[i] = make([]int.len(arr))
	}
	dp[0] [0] = grid[0] [0]
	for i := 0; i < l; i++ {
		for j := 0; j < len(grid[i]); j++ {
			if i == 0&& j ! =0 {
				dp[i][j] = dp[i][j- 1] + grid[i][j]
			} else if j == 0&& i ! =0 {
				dp[i][j] = dp[i- 1][j] + grid[i][j]
			} else ifi ! =0&& j ! =0 {
				dp[i][j] = min(dp[i- 1][j], dp[i][j- 1]) + grid[i][j]
			}
		}
	}
	return dp[l- 1] [len(dp[l- 1])- 1]}func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
Copy the code

Running results:

Again, running the above code, we find that we are using too much memory. Is there any way to compress memory? Through observation, we find that in the process of calculating the minimum path sum of each node from the upper left corner to the lower right corner, we only need to use the data that has been accumulated before, and will not access the previous element data again. (See if this process is similar to minesweeping. In fact, if you study the minesweeping plug-in, you will find that there is a similar analysis method in the core algorithm of minesweeping. I won’t go into the details here.)

The optimized code looks like this:

func minPathSum(grid [][]int) int {
	l := len(grid)
	if l < 1 {
		return 0
	}
	for i := 0; i < l; i++ {
		for j := 0; j < len(grid[i]); j++ {
			if i == 0&& j ! =0 {
				grid[i][j] = grid[i][j- 1] + grid[i][j]
			} else if j == 0&& i ! =0 {
				grid[i][j] = grid[i- 1][j] + grid[i][j]
			} else ifi ! =0&& j ! =0 {
				grid[i][j] = min(grid[i- 1][j], grid[i][j- 1]) + grid[i][j]
			}
		}
	}
	return grid[l- 1] [len(grid[l- 1])- 1]}func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
Copy the code

Running results:

Thinking after class: How is the path and class problem different from the subsequence class problem?

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