LeetCode偶尔一题-64-最小路径和

题目描述

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明 ：每次只能向下或者向右移动一步。
示例:

输入:
[

[1,3,1],  
[1,5,1],  
[4,2,1]  

]
输出 : 7
解释: 因为路径 1→3→1→1→1 的总和最小。

分析题目

递归

对于有些题目，如果我们一下子想不出来解题思路，其实可以稍微对它分析一下，那么自然就会找到解题的办法。
根据题中描述，我们知道 每次只能向下或者向右移动一步，我们以此为依据画出示例中所有可能的路径????

很明显这是一个树形结构，我们只要算出每个 头结点 到叶子结点 所经过的路径和，它们中最小的值就是题目中要求的 最小路径和 ，因此我们可以尝试用 深度优先搜索 来解决它，第一版程序????

var minPathSum = function (grid) {return dfs(0, 0)
    function dfs (i, j) {if (i === grid.length || j === grid[0].length) {return Number.MAX_SAFE_INTEGER}
        if (i === grid.length - 1 && j === grid[0].length - 1) {return grid[i][j]
        }
        return grid[i][j] + Math.min(dfs(i + 1, j), dfs(i, j + 1))
    }
}

动态规划

细心的你可能已经发现，这道题其实可以把它分解为一个个子问题，而我们只要解决了子问题，那么只要把子问题合并起来就能给出解。
怎么说呢？原题目让我们求到 grid[i][j] 的最小路径，那么我们只要找到 grid[i][j] 的 上一个 或者 左一个 中和它加起来最小的一个。换成代码也就是求???? min = Math.min(grid[i][j] + grid[i - 1][j], gird[i][j] + grid[i][j-1])

具体实现如下????

var minPathSum = function(grid) {let x = grid.length - 1, y = grid[0].length - 1
    for (let i = 0; i <= x; i++) {for (let j = 0; j <= y; j++) {let tmp = grid[i][j]
            if (j === 0) {if (i > 0) {grid[i][j] = grid[i - 1][j] + tmp
                }
            } else {if (i > 0) {grid[i][j] = Math.min(grid[i - 1][j] + tmp, grid[i][j - 1] + tmp)
                } else {grid[i][j] = grid[i][j - 1] + tmp
                }
            }
        }
    }
    return grid[x][y]
};

原题地址: https://leetcode-cn.com/probl…
代码不定时更新，欢迎 star 我的 repo

扫描下方的二维码或搜索「tony 老师的前端补习班」关注我的微信公众号，那么就可以第一时间收到我的最新文章。