The title

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:

Input: grid = [[1,3,1],[1,5,1]]

Output: 7

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

LeetCode portal: 64. Minimum path sum

The problem solving

First let’s show a bad algorithm with O(2^(n+m-1)) time, which was my first answer 😂.

Violence law

So the idea is that you start at (0,0) and then you go to (0,1) and (1,0) and then you go down and you get 2 to the n plus m minus 1 in perfect time

/ * * *@param {number[][]} grid
 * @return {number}* /
var minPathSum = function (grid) {
    const { length: m } = grid
    const { length: n } = grid[0]
    // By default, the sum of all walks is infinite
    const sums = [Infinity]
    goNext(grid, m, n, 0.0.0, sums)
    return sums[0]};/ * * *@param {number[][]} Grid m * n@param {number} M the number of lines in the grid *@param {number} N Number of columns in the grid *@param {number} X x star@param {number} Y, y coordinate *@param {number} Sum Indicates the sum of the current path *@param {number[]} The sums are sums. The final result *@return {number}* /
function goNext(grid, m, n, x, y, sum, sums) {
    // Determine whether to complete the journey
    if (x === n - 1 && y === m - 1) {
        const res = sum + grid[y][x]
        // Is it smaller than the smallest result? If so, keep it
        sums[0] = Math.min(sums[0], res)
        // console.log(sums[0])
    }
    // Total distance traveled
    sum += grid[y][x]
    // Out of bounds and whether the minimum distance is exceeded
    if (x + 1 < n && sum < sums[0]) {
        // Go right without crossing the boundary
        goNext(grid, m, n, x + 1, y, sum, sums)
    }
    // Out of bounds and whether the minimum distance is exceeded
    if (y + 1 < m && sum < sums[0]) {
        // Go down without crossing the boundary
        goNext(grid, m, n, x, y + 1, sum, sums)
    }
}
Copy the code

Just to give you a sense of how bad this algorithm is

Data Open up the page and click three left mouse clicks in the body to select all the data and control + C will copy the data (40,000 data)

I can’t figure it out at all with this solution, so if you console.log my computer’s paths add up to 1634 at most and I can’t get any smaller than that, I’m still there.

Now I’m going to introduce you to the solution of dynamic programming

Dynamic programming

Here’s the idea:

An array of m x n is used to record the minimum sum of paths from (0,0) to each point on the grid, and the answer is solved when the last point (m-1,n-1) is recorded.

So how do you know the minimum path that you need to take to get to each point?

In fact, there are at most two ways to get to any point:

1. Go down (down from the top)

2. Go to the right (come from the left)

We just need to choose the two paths and the smallest one to get there

Let’s analyze all the points on this grid and actually divide them into three parts:

The first part is the starting point (0,0). There is no doubt that the distance passed by the point (0,0) is the grid[0][0] itself.

2. The second part is the point I = 0 and the point j = 0 and this part when I = 0 represents the left boundary which means that you can’t get to this point from the left you can only go down, and when j = 0 represents the top which means that you can’t get to this point from the top you can only get to this point from the left. So the only direction we have to think about when we calculate is the distance closest to us on the left or the distance closest to us on the right plus our distance.

3. The points of the third part, that is, all points except those mentioned in the preceding two parts, can be reached from both directions, that is, from above and from the left. So when we calculate, we just need to choose two directions with the shortest distance.

So we can figure out the minimum distance to go through all the points.

Let’s look at the code

var minPathSum = function (grid) {
    const { length: m } = grid,
        { length: n } = grid[0]
    // create a new dynamic programming array to record the minimum path sum of each point on the grid starting from (0,0).
    const dp = []
    / / traverse line
    for (let i = 0; i < m; i++) {
        // Complete the child elements of dp
        dp[i] = []
        / / traverse
        for (let j = 0; j < n; j++) {
            Grid [0][0]
            if (i === 0 && j === 0) {
                dp[0] [0] = grid[0] [0]
                // If it is the left boundary then the distance directly itself plus the distance in the direction of top is enough
            } else if (i === 0) {
                dp[0][j] = dp[0][j - 1] + grid[0][j]
                // If it is the top then the distance of the direct itself plus the distance of the left direction can be used
            } else if (j === 0) {
                dp[i][0] = dp[i - 1] [0] + grid[i][0]
                // The remaining points can be reached in 2 ways, so choose the smallest one plus its own distance
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
            }
        }
    }
    // Return the answer
    return dp[m - 1][n - 1]};Copy the code

So if you take that data again and you can calculate in a flash the minimum path that you need to go from 40,000 points to the last point is 823.

Is it very simple 😬, let’s look at the results after submission.

Submit the test

Beat 69% of js algorithms.

The time complexity of this algorithm is O(MXN), which is already very fast