This is the 18th day of my participation in the August Challenge

preface

LeetCode array type problem related solution, can be seen before doing LeetCode array type problem must see, classification solution summary question, can be used to improve each item. If you feel helpful, please remember to pay attention to it. Thank you!

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: grid = [[1,3,1],[1,5,1]]

Output: 7

Explanation: Because path 1→3→1→1→1 has the smallest sum.

Example 2: input: grid = [[1,2,3],[4,5,6]] output: 12

Link: leetcode-cn.com/problems/mi…

Answer key

  1. Path [I][j] = min(path[i-1][j], path[I][j-1]) + grid[I][j] For example, if path[I][j-1] is used in the calculation of path[I][j], Path [I +1][j-1] (path[I +1][j-1] = path[I][j-1] + path[I][j-2]); The next time the value is used, it can be retrieved rather than double-counted.

    The specific solution is shown in the following code, where the PATH array represents the memory array. When the corresponding element is -1, it means that it has not been calculated; when it is not -1, it means that it has been calculated and can be returned directly.

    Time complexity O(mn), space complexity O(mn)

/ * * *@param {number[][]} grid
 * @return {number}* /
var minPathSum = function(grid) {
  const m = grid.length
  const n = grid[0].length
  // Memory array
  const path = Array.from({ length: m }, () = > (new Array(n).fill(-1)))
  
  const minPath = (x, y) = > {
    // Get to the starting point
    if (x === 0 && y === 0) return grid[0] [0]
    // Out of the boundary
    if (x < 0 || y < 0) return Number.MAX_VALUE
    // The corresponding position in the memory array has been calculated
    if(path[x][y] ! = = -1) {
      return path[x][y]
    } 
    / / recursion
    path[x][y] = grid[x][y] + Math.min(minPath(x-1, y), minPath(x, y-1))
    return path[x][y]
  }
  
  return minPath(m-1, n-1)};Copy the code
  1. Dynamic programming. In general, if a problem can be solved by memorization recursion, it can also be solved by dynamic programming. Mnemonic recursion works from end to end, whereas dynamic programming works from end to end. What does that mean? Is that we calculated from the starting point, the path [0] [0] = grid [0] [0], the points on the boundary with the path [I] [0] = path [0] + [I – 1] grid [I] [0], the path [0, j] = path [0, J – 1] + grid [0, j], then the internal point of a path [I] [j] = min (path [j] + [I – 1] path [I]] [j – 1) + grid [I] [j], thus realize the way from the beginning to the end.

See the code below. One thing to note is that we use the grid array instead of the path array to reduce space complexity.

Time complexity O(Mn), space complexity O(1)

/ * * *@param {number[][]} grid
 * @return {number}* /
var minPathSum = function(grid) {
    let m = grid.length;
    if (m == 0) return 0;
    let n = grid[0].length;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (i === 0 && j === 0) continue;
            if (i === 0)
                grid[i][j] += grid[i][j-1]
            else if (j === 0) 
                grid[i][j] += grid[i-1][j]
            else 
                grid[i][j] += Math.min(grid[i][j-1], grid[i-1][j])
        }
    }   
    return grid[m - 1][n - 1];
};
Copy the code