preface
Today is the third day of our presentation on the path problem in dynamic programming.
Today’s topic is mainly to consolidate the DP analysis skills I shared with you last time.
In addition, AT the end of the article, I listed the related topics about the path problem that I sorted out.
I will explain the path problems in the arranged order (one a day).
You can also try to do it first, you are welcome to leave a message to me, you feel related to the path of DP type topic ~
Topic describes
This is 64. Minimum path sum on LeetCode, Medium difficulty.
Given an M x N grid with non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path.
Note: you can only move one step down or right at a time.
Example 1:
Input: the grid = [,3,1 [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 codeExample 2:
Input: grid = [[1,2,3],[4,5,6]] output: 12Copy the codeTip:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 200
- 0 <= grid[i][j] <= 100
Dynamic programming solution
This problem adds the concept of path cost on the basis of 62. Different paths.
We can adjust our “state definition” according to the question:
Define f[I][j] as the minimum sum from (0,0) to position (I,j).
So f[n-1][m-1] is our final answer, f[0][0]=grid[0][0] is an obvious starting state.
We can only move down or to the right, so we can move from the current position to the right.
-
F [I][j] = f[i-1][j] + grid[I][j]
-
F [I][j] = f[I][j] + grid[I][j]
-
Can pass down the current position can move to the right, that is f [I] [j] = min (f [1], [I] f [j] [I – 1]) + grid [I] [j].
Code:
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] f = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
f[i][j] = grid[i][j];
} else {
int top = i - 1> =0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
int left = j - 1> =0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE; f[i][j] = Math.min(top, left); }}}return f[m - 1][n - 1]; }}Copy the code- Time complexity: O(n∗m)O(n*m)O(n∗m)
- Space complexity: O(n∗m)O(n*m)O(n∗m)
The advanced
- What if I wanted to print the path with the lowest sum? (If there are multiple answers, return one of them.)
We know from the original problem, we need to go from 0,0 to m minus 1,n minus 1.
That is, we need to scan the entire square (transfer all the states) to get the answer.
So, obviously, we can use additional data structures to record how we move step by step to f[m-1][N-1].
When the entire DP process is complete, we push our path back and forth with data structures that assist recording.
At the same time, since our original DP part has created a two-dimensional array to store the status values, this time we use a one-dimensional array to record the G array used to record the “previous step”.
Code:
class Solution {
int m, n;
public int minPathSum(int[][] grid) {
m = grid.length;
n = grid[0].length;
int[][] f = new int[m][n];
int[] g = new int[m * n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
f[i][j] = grid[i][j];
} else {
int top = i - 1> =0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
int left = j - 1> =0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
f[i][j] = Math.min(top, left);
g[getIdx(i, j)] = top < left ? getIdx(i - 1, j) : getIdx(i, j - 1); }}}// Start from "end", find "previous" in g[] array
int idx = getIdx(m - 1, n - 1);
// Add pathpoints to the path array in reverse order
int[][] path = new int[m + n][2];
path[m + n - 1] = new int[]{m - 1, n - 1};
for (int i = 1; i < m + n; i++) {
path[m + n - 1 - i] = parseIdx(g[idx]);
idx = g[idx];
}
// Sequential output positions
for (int i = 1; i < m + n; i++) {
int x = path[i][0], y = path[i][1];
System.out.print("(" + x + "," + y + ")");
}
System.out.println("");
return f[m - 1][n - 1];
}
int[] parseIdx(int idx) {
return new int[]{idx / n, idx % n};
}
int getIdx(int x, int y) {
returnx * n + y; }}Copy the codeYou might think that the code for the “output” scenario is too much trouble.
This is because we find the path “backwards”, and output solutions “along” output.
If we want to simplify the process of finding a path, we need to perform an equivalent transformation of the original problem:
Convert “shortest path from (0,0) to (m-1,n-1)” to “shortest path from (m-1,n-1) to (0,0)”, and move direction from “down & right” to “up & left”.
In this way, we can implement the “find path” order and “output” order in the same direction.
Adjust the definitionf[i][j]For from(m-1,n-1)Start to reach position(i,j)The minimum sum of.
class Solution {
int m, n;
public int minPathSum(int[][] grid) {
m = grid.length;
n = grid[0].length;
int[][] f = new int[m][n];
int[] g = new int[m * n];
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
if (i == m - 1 && j == n - 1) {
f[i][j] = grid[i][j];
} else {
int bottom = i + 1 < m ? f[i + 1][j] + grid[i][j] : Integer.MAX_VALUE;
int right = j + 1 < n ? f[i][j + 1] + grid[i][j] : Integer.MAX_VALUE;
f[i][j] = Math.min(bottom, right);
g[getIdx(i, j)] = bottom < right ? getIdx(i + 1, j) : getIdx(i, j + 1); }}}int idx = getIdx(0.0);
for (int i = 1; i <= m + n; i++) {
if (i == m + n) continue;
int x = parseIdx(idx)[0], y = parseIdx(idx)[1];
System.out.print("(" + x + "," + y + ")");
idx = g[idx];
}
System.out.println("");
return f[0] [0];
}
int[] parseIdx(int idx) {
return new int[]{idx / n, idx % n};
}
int getIdx(int x, int y) {
returnx * n + y; }}Copy the code- If there is a negative weight in the square, how do I solve it?
If you consider adding negative weights to a square, you naturally need to add a restriction: each cell can only be accessed once, otherwise there will be an infinite number of paths to the negative weight cell.
At this point, the problem is transformed into a “graph theory” problem, a “minimum spanning tree” problem.
The two directions to the right and down of each cell were regarded as two undirected edges and solved by Prim algorithm /Kruskal algorithm.
We’ll talk about that later in graph theory.
conclusion
Today, IN addition to the original LeetCode problem, I also introduced two “advanced” problems.
In the “advanced one” output scheme problem, I showed you how to use a “one-dimensional array” to store “two-dimensional information”, which is a common device. And how to reduce coding difficulty through problem equivalence transformation.
I showed you, in advance two, that the same problem with a different premise can be solved in a very different way.
After changing a precondition, the proof corresponding to the original solution will be invalid, and the original algorithm will not be able to solve correctly.
I asked a similar question in the first lecture of the path problem, Thinking.
And that’s why we have to prove it when we do algorithms, because if we get to the bottom of it, we can do it.
Path problem (directory)
62. Different Paths (medium) : Lecture 1 on paths
63. Different Paths II (Medium) : Lecture 2 on paths
64. Minimum path and (medium) :
120. Triangle minimum Path sum (medium)
Minimum and (moderate) descent path
1289. Descent path minimum and II (difficulty)
1575. Counting all possible paths (difficulty)
576. Number of paths out of bounds (medium)
1301. Number of paths for maximum score (difficulty)
Welcome to add ~
The last
This is the 64th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have locks. We will finish all the questions without locks first.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.
- This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign