The topic of dry

Given a *m* x * N * grid of non-negative integers, find a path from the top left to the bottom right that minimizes the sum of the numbers along the path.

** Indicates that ** can move down or right only 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

Solution: moving gauge

This problem is really calculating the minimum along the path, so the first thing that comes to mind is also dynamic programming.

We use the five parts of the moving gauge to analyze the following whole process:

Dp [I][j] indicates the minimum value reached at the position I, I.

2. Summarize the recurrence formula: because we can only down or to the right, so our dynamic formula for dp [I] [j] = min (dp [j], [I – 1] dp [I]] [j – 1) + dp [I] [j].

Notice that there’s no right or up case on both boundaries, so we’re going to classify it

3. How to initialize dp array: dp array should be the same size as GIRD array

4. Determine the order of traversal: traversal backwards from zero

Code implementation:

Execution time: 128 ms, beating 8.15% of all JavaScript commits

Memory consumption: 44.7 MB, beating 5.03% of all JavaScript commits

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