This is the seventh day of my participation in the August More text Challenge. For details, see:August is more challenging

Minimum path sum (question number 64)

The title

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 numbers on the path.

Note: You can only move down or to the right one step at a time.

Example 1:

Input: grid = [[1.3.1], [1.5.1], [4.2.1]] output:7Explanation: Because of the path1-3-1-1-1The sum of PI is the smallest.Copy the code

Example 2:

Input: grid = [[1.2.3], [4.5.6]] output:12
Copy the code

Tip:

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

link

Leetcode-cn.com/problems/mi…

explain

This one, this one is classical dynamic programming.

Although is medium topic, but the author feels it does not deserve.

The first row has no elements on it, so you can only go to the left. This is easy to do:

for (let i = 0; i < n; i++) {
  dp[0][i] = i ? grid[0][i] + dp[0][i - 1] : grid[0][i]    
}
Copy the code

I could do the first column now, but I don’t think I need to, but I could do it inside the loop, but I won’t do it here.

Then the next step is to work out the DP formula. The formula here does not have much complex logic. To reach a block, you can only walk from the top or left of the block and take the minimum value.

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

Right? Very simple. Now don’t forget to deal with the first block in each column, because there are no elements to the left of these blocks, so they can only come down from the first block in the previous column, so the values of these blocks are:

dp[i][j] = dp[i - 1][j] + grid[i][j]
Copy the code

So now you can go through two levels of loop to get all the DP values, and then choose the last one according to the question.

At this point, simple dynamic programming is complete, so let’s look at the code.

Your own answers (even numbers)

var minPathSum = function(grid) {
  const m = grid.length
  const n = grid[0].length
  const dp = Array.from({length: m}, () = > new Array(n).fill(0))
  for (let i = 0; i < n; i++) {
    dp[0][i] = i ? grid[0][i] + dp[0][i - 1] : grid[0][i]    
  }
  for (let i = 1; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if(! j) { dp[i][j] = dp[i -1][j] + grid[i][j]
      } else {
        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

The logic of this part is the same as what is said in the explanation, there is no difference. At this time, the time can reach 90%, and the memory consumption is about 70%, which proves that there is still room for optimization in the space complexity. The optimization here is also a classic dynamic programming dimension reduction optimization 👇.

Your own answer (dimension reduction)

As mentioned above, the classic way to reduce the space complexity is to reduce the DP array from two dimensions to one dimension, which is completely feasible and very simple.

Back to the topic, the minimum value of each piece and it only above and to the left of the block, then can only maintain a one-dimensional array, the array is treated as a top row every time can, then updates from the left, so the current position to the left of the values can be as the value of this line, value as a line on the behind, so can.

var minPathSum = function(grid) {
  const m = grid.length
  const n = grid[0].length
  const dp = new Array(n)
  for (let i = 0; i < n; i++) {
    dp[i] = (i ? dp[i - 1] : 0) + grid[0][i]
  }
  for (let i = 1; i < m; i++) {
    for (let j = 0; j < n; j++) {
      dp[j] = (j ? Math.min(dp[j - 1], dp[j]) : dp[j]) + grid[i][j]
    }    
  }
  return dp[n - 1]};Copy the code

So you can use a one-dimensional array to solve this problem, the final answer is the last element of an array of DP, two for loop in this code with a judge j exists inside the code, the logic here will not be able to carry out, because each line of the first element of the need to real-time calculation, and this is also the solutions of the above differences.

A better way

There is no




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)