Topic describes

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 code

Example 2:

Input: grid = [[1,2,3],[4,5,6]] output: 12Copy the code

Tip:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= gridi <= 100

Answer key

This is a typical dynamic programming problem, which can be used as a starting point, but is a little more complicated than climbing stairs.

Just to get a sense of the concept, dynamic programming, it’s essentially recursive, it’s repetitive, but the difference with recursion is that you break the problem down into optimal subproblems, and optimal subproblems, which means that the optimal subproblem represents the best way to solve the problem most of the time. If you know divide-and-conquer, the difference between dynamic programming and divide-and-conquer is that divide-and-conquer is dividing for the sake of dividing, it doesn’t matter if it’s optimal, there may be double calculations between each subproblem; And dynamic programming is to find the optimal solution, a fatal blow to find the best solution, a complex problem into a number of sub-problems, each sub-problem is independent of each other, and finally combine the values of these sub-problems, get the final solution.

In this case, to go from the top left corner to the bottom right corner, you have to find a path where the sum of the values is the smallest. Grid [m][n] is the minimum number of rows from grid[0][0] to grid[m][n]. If we use I and j to represent the pointer to the row and column, then if we can get the minimum value to grid[I][j], it is the key to solve the problem. Then we use dp[I][j] to represent the minimum path to the current point.

So for the grid[I][j], to go to the current location, either above it or to the left of it, take the minimum of both paths, plus the point itself. The expression test is like this:

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

If I =0 or j=0, that is, if the current point is on the left side or the first row, then the above formula does not work and needs to be listed separately:

Dp [I][0] = dp[i-1][0]+ grid[I][0]; // In line 1 dp[0][j] = DP [0][j-1]+ grid[0][J-1]Copy the code

The complete code looks like this:

/** * @param {number[][]} grid * @return {number} */ var minPathSum = function(grid) { if (grid == null || grid.length == 0 || grid[0].length == 0) { return 0; } var r = grid.length, c = grid[0].length; var dp = Array.from(new Array(r),() => new Array(c)); dp[0][0] = grid[0][0]; for (var i = 0; i < r; i++) { for (var j = 0; j < c; J ++) {// on the first line if(I ===0&&j! ==0) dp[i][j] = dp[i][j - 1] + grid[i][j]; Else if(I! == 0&& j===0) dp[i][j] = dp[i-1][j] + grid[i][j]; else if(i! ==0&&j! ==0) dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[r - 1][c - 1]; };Copy the code

The routine of dynamic programming problems is to find your dynamic transition equation: DP, which is the soul of dynamic programming; Another important point is that this equation must have a critical value, and this value can be directly out of the result, with the equation and a constant critical value, you can rely on the powerful computing power of the computer, recursive calculation of all the values, and finally merged into the result.

Complexity analysis

Time complexity: O(Mn)

Space complexity: O(mn), and I’ll explain that, because I’m creating a two-dimensional array, so it’s O(mn).

Title link: leetcode-cn.com/problems/mi…