Topic describes

Given an m x n grid containing non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers on the path. You can only move down or to the right one step 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 code

The original problem is here

Depth-first search

I used depth-first traversal to do this problem at first, and also did pruning, but the result was definitely over time

void dfs(int row,int line,int rowMax,int lineMax,int sum,int[][] grid){
        if(sum>min)
            return;
        if(row>rowMax-1||line>lineMax-1)
            return;
        if(row==rowMax-1&&line==lineMax-1){
            sum += grid[row][line];
            max = Math.min(max,sum);
            sum -= grid[row][line];
            return;
        }
        sum += grid[row][line];
        dfs(row+1,line,rowMax,lineMax,sum,grid);
        dfs(row,line+1,rowMax,lineMax,sum,grid);
        sum -= grid[row][line];
    }
Copy the code

So this is the key code for DFS, and I’m not going to write the main code, so you go one step down or one step to the right, and then on each walk you check if sum is greater than min, and if sum is greater than min, you don’t need to go through it again, you just return, and then at the end of each walk you update min. The result was a relentless timeout…

Dynamic programming of two-dimensional DP arrays

And then we looked at the solution, and we found that we could use dynamic programming. So the key to dynamic programming here is that you take the minimum, and you can only move down or to the right at a time, so that the minimum sum at each position is determined only by the elements above or to the left, because that’s the only way to get to the current position. Because of this property, we can use dynamic programming, let’s say that the result array is DP, and each time we go to a position I,j, where the minimum sum is zero

dp[i][j] + Math.min(dp[i-1][j],dp[i][j-1]);
Copy the code

Of course, I and j are 0, which is where the first row and the first column are to be discussed separately, because they don’t have anything on the top or on the left.

class Solution { public int minPathSum(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; for (int i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for (int j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[m - 1][n - 1]; }}Copy the code

So you can write your code like this, and they tell you that m,n is between 1 and 200, and you don’t have to write boundary conditions

Dynamic programming of one-dimensional DP arrays

But this feeling is with a little more space, we actually only need one final dp [m – 1) [n – 1), and then to the left of the value of each position and it actually related to the above elements, and the 2 d array of dp, the remaining so many lines, finally also just the last line, before the finish line with the wouldn’t work, then based on this idea, We can just use a one-dimensional DP array

int m = grid.length; int n = grid[0].length; int[] res = new int[n]; Res [0] = grid[0][0]; for(int i=1; i<n; ++i) res[i] = res[i-1] + grid[0][i]; for(int i=1; i<m; ++i){ res[0] += grid[i][0]; for(int j=1; j<n; ++j){ res[j] = grid[i][j] + Math.min(res[j],res[j-1]); } } return res[n-1];Copy the code

The key code is here

res[j] = grid[i][j] + Math.min(res[j],res[j-1]);
Copy the code

When the position is updated line by line each time, the res[j] on the right side of the expression can be understood as the minimum path sum of the upper element (because res[j] has not been updated at this time), and res[j-1] is the minimum path sum of the left element of this element, and then the above code can be used to update.

Dynamic programming without extra space

We look at the code above can be found that the grid in the matrix of every element also is called only once (the first row and first column element is called twice), and subject to have said that the original matrix cannot be modified, so we can directly in the matrix operation, the first of the first row and first column elements, modified to modify other elements, The code is as follows:

int m = grid.length; int n = grid[0].length; for(int i=1; i<n; ++i) grid[0][i] += grid[0][i-1]; for(int i=1; i<m; ++i){ grid[i][0] += grid[i-1][0]; for(int j=1; j<n; ++j){ grid[i][j] = grid[i][j] + Math.min(grid[i-1][j],grid[i][j-1]); } } return grid[m-1][n-1];Copy the code

I’m just going to modify the original matrix, and I’m going to modify it in the same way as if the DP array was two-dimensional, and I can do that, mainly because I only need the final value, and it doesn’t matter if the original matrix is not recognizable. And every value in the Grid matrix that you use once will never be used again, so it’s ok to change it.