64. Minimum Path Sum

Leetcode link

题目简介

/**
 * @param {number[][]} grid
 * @return {number}
 */

题目给我们一个全是数字的表格 grid

要求我们选中一条途径数字之和最小的路径从表格的左上走到右下

并返回该路径途径数字之和

解题思路

我们先讨论只有一个格子的情况，此时答案就是 grid[0][0] 的值

如果有两个格子呢？假设是左右相邻，此时答案是 grid[0][0] + grid[0][1]

再次拓展到 4 个格子的情况：右下角的格子有两条路径，我们需要选择其中和比较小的作为路径，此时答案为 min(grid[0][1], grid[1][0]) + grid[1][1]

假设我们使用数组 dp 来表示到达当前格子的最少路径之和

根据上面的讨论，我们得到了状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

为了方便计算，我们可以声明一个长宽都比 grid 多 1 的数组，并且将其中元素全部初始化为正无穷

dp 数组的初始状态为 dp[1][1] = grid[0][0]

Javascript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
    const width = grid[0].length
    const height = grid.length
    const dp = Array.from({ length: height + 1 }, _ => new Array(width + 1).fill(Number.MAX_SAFE_INTEGER))

    for (let row = 1; row <= height; row++) {
        for (let col = 1; col <= width; col++) {
            if(row === 1 && col === 1) {
                dp[row][col] = grid[0][0]
                continue
            }
            dp[row][col] = grid[row - 1][col - 1] + Math.min(dp[row - 1][col], dp[row][col - 1])
        }
    }

    return dp[height][width]
};