LeetCode64题：最小路径问题（动态规划入门）-一一网

题目

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]

输出：7

解释：因为路径 1→3→1→1→1 的总和最小。

LeetCode传送门: 64.最小路径和

解题

首先我们来展示一个时间复杂度为 O(2^n)的糟糕算法，也就是我第一次的答案?。

暴力法

思路是这样的从 (0，0) 点开始进行下一步分别走到点 (0,1) 和 (1,0) 然后接着向下走这样时间复杂度完美的变成了 2 的 n 次方（假设网格是正方形的）

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function (grid) {
    const { length: m } = grid
    const { length: n } = grid[0]
    // 默认走完全程总和是无穷大的
    const sums = [Infinity]
    goNext(grid, m, n, 0, 0, 0, sums)
    return sums[0]
};
/**
 * @param {number[][]} grid m * n 的网格
 * @param {number} m 网格的行数
 * @param {number} n 网格的列数
 * @param {number} x x坐标
 * @param {number} y y坐标
 * @param {number} sum 当前路径的和
 * @param {number[]} sums 走完全程最终结果
 * @return {number}
 */
function goNext(grid, m, n, x, y, sum, sums) {
    // 判断是否走完全程
    if (x === n - 1 && y === m - 1) {
        const res = sum + grid[y][x]
        // 是否比最小的结果还要小如果是则保留
        sums[0] = Math.min(sums[0], res)
        // console.log(sums[0])
    }
    //累计走过的路程
    sum += grid[y][x]
    //越界判断和是否超过最小路程
    if (x + 1 < n && sum < sums[0]) {
        // 不越界的情况下接着向右走
        goNext(grid, m, n, x + 1, y, sum, sums)
    }
    //越界判断和是否超过最小路程
    if (y + 1 < m && sum < sums[0]) {
        // 不越界的情况下接着向下走
        goNext(grid, m, n, x, y + 1, sum, sums)
    }
}
复制代码

给大家个数据感受下这个算法糟糕的性能

data 打开这个网页然后在body中单击三下鼠标左键就能全部选中数据然后 control + c 就能复制好这个数据了（4万个数据）

用这个解法就是完全算不出来，大家可以 console.log 一下我的计算机路径总和最多算到 1634 我就算不出更小的了，一直不动。

接下里给大家介绍一下动态规划的解法

动态规划

思路是这样的:

用一个 m x n 的数组来记录网格上从（0，0）点出发到达的每一个点所经历的最小路径和，记录到最后一个点（m-1,n-1）的时候也就求出了答案。

那么怎么知道达到每个点所需要的经过的最小路径呢？

其实要到达任意一个点最多只有2种可能：

1、向下走（从上面走下来）

2、向右走（从左边走过来）

我们只需要选择这两种情况路径和最小的一种即可达到目的

我们来分析一下这个网格上所有的点其实可以分为三个部分：

1、第一个部分就是起点 (0,0) 毫无疑问经过 (0,0) 点经过的路程就是 grid[0][0] 本身。

2、第二个部分就是 i = 0 的点和 j = 0 的点这个部分当 i = 0 时表示的是左边界说明不可能从左边达到该点只能从上往下走，当 j = 0 时表示的是顶部说明不可能从上边到达这些点只可能从左边到达。所以我们在计算的时候只需要考虑一个方向就是左边最靠近自己的路程或者右边最靠近自己路程加上本身的路程即可。

3、第三个部分的点，也就是除了上面两个部分所说的所有点，都能从两个方向到达即既能从上面到达又能从左边到达。所以我们在计算的时候只需要选两个方向上路程较小的方向即可。

这样我们就能够求出经历所有的点的最小路程。

让我们来看下代码

var minPathSum = function (grid) {
    const { length: m } = grid,
        { length: n } = grid[0]
    // 新建动态规划数组记录网格上从（0，0）点出发到达的每一个点所经历的最小路径和。
    const dp = []
    // 遍历行
    for (let i = 0; i < m; i++) {
        // 完善 dp 的子元素
        dp[i] = []
        // 遍历列
        for (let j = 0; j < n; j++) {
            // 如果是起点那么经过的路程就是grid[0][0]
            if (i === 0 && j === 0) {
                dp[0][0] = grid[0][0]
                //如果是左边界那么直接本身的路程加上top方向上的路程即可
            } else if (i === 0) {
                dp[0][j] = dp[0][j - 1] + grid[0][j]
                //如果是顶部那么直接本身的路程加上left方向上的路程即可
            } else if (j === 0) {
                dp[i][0] = dp[i - 1][0] + grid[i][0]
                //剩下的点都有可能有2种方式达到所以择优选择一个最小的加上本身的路程即可
            } else {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
            }
        }
    }
    // 返回答案
    return dp[m - 1][n - 1]
};
复制代码