leetcode 64. 最小路径和

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

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

题解：

1.一个包含非负整数的 m x n 网格

2.从左上角到右下角的路径，找出一条路径和最小

3.每次只能向下或者向右移动一步

4.题目本质上和174. 地下城游戏一样

示例:

输入:

[[1,3,1],

  [1,5,1],

  [4,2,1]]

输出: 7

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

解题思路：

• 和174. 地下城游戏一样思路，考虑倒序

• 因为都为非负整数，可以从0开始累计路径和

• 累加每一步下方和右方最小的路径节点，从而能得到一个路径和最小

• 最后回到dp左上角的位置得到一个路径最小的和

C/C++题解：

class Solution {

public:

    int minPathSum(vector<vector<int>>& grid) {

        int n = grid.size(), m = grid[0].size();

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, INT_MAX));

        dp[n][m - 1] = dp[n - 1][m] = 0;//都为非负整数，从0累计路径和

        for (int i = n - 1; i >= 0; i--) {

            for (int j = m - 1; j >= 0; j--) {//从尾模拟往右、下走的过程

                dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1]);}}

                // 累加每一步下方和右方最小的路径节点，从而能得到一个路径和最小的

        return dp[0][0];}};//回到左上角得到一条路径的最小和

Debug结果：

Java题解：

class Solution {

    public int minPathSum(int[][] grid) {

        int n = grid.length, m = grid[0].length;

        int[][] dp = new int[n + 1][m + 1];

        for(int i=0;i<dp.length;i++){

            for(int j=0;j<dp[i].length;j++){

                dp[i][j] = Integer.MAX_VALUE; } }

        dp[n][m - 1] = dp[n - 1][m] = 0;//都为非负整数，从0累计路径和

        for (int i = n - 1; i >= 0; i--) {

            for (int j = m - 1; j >= 0; j--) {//从尾模拟往右、下走的过程

                dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], dp[i][j + 1]);}}

                // 累加每一步下方和右方最小的路径节点，从而能得到一个路径和最小的

        return dp[0][0];}}//回到左上角得到一条路径的最小和

Debug结果：

Python题解：

class Solution(object):

    def minPathSum(self, grid):

        """:type grid: List[List[int]]:rtype: int"""

        n, m  = len(grid), len(grid[0])

        dp = [[sys.maxint for _ in range(m+1)] for _ in range(n+1)]

        dp[n][m - 1] = dp[n - 1][m] = 0 #都为非负整数，从0累计路径和

        for i in range(n-1, -1, -1):

            for j in range(m-1, -1, -1):

                dp[i][j] = grid[i][j] + min(dp[i + 1][j], dp[i][j + 1])

            #累加每一步下方和右方最小的路径节点，从而能得到一个路径和最小的

        return dp[0][0] #回到左上角得到一条路径的最小和

Debug结果：

更多题解移步公众号免费获取