Leetcode: 【每日一题】- 2019-08-08 - 64.最小路径和

[azl397985856]

难度： 中等
标签 数组，动态规划
题目描述：

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

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

示例:

输入:
[
  [1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[xiongcaihu]

``` .js
/**

• @param {number[][]} grid
• @return {number}
• 
  
  
  
  • 动态规划
  
  
• 
  
  
  
  • 假设走到终点的最短路径和是F(x,y)
  
  
• 
  
  
  
  • 那么他的上一步肯定是 从 Math.min(F(x-1,y),F(x,y-1)) 中比较小的那一个位置过来
  
  
• 
  
  
  
  • 所以规律是
  
  
• 
  
  
  
  • F(x,y) = min(F(x-1,y),F(x,y-1)) + grid[x][y]
  
  
• 
  */
  var minPathSum = function (grid) {
  var map = Array.from({
  length: grid.length
  }, () => new Array(grid[0].length));
  return temp(grid.length - 1, grid[0].length - 1);

function temp(x, y) {
    if (map[x][y]) {
        return map[x][y];
    }
    var min = 0;
    if (x == 0 || y == 0) {
        while (y >= 0) {
            min += grid[x][y];
            x == 0 ? y-- : x--;
        }
    } else {
        min = Math.min(temp(x - 1, y), temp(x, y - 1)) + grid[x][y];
    }

    map[x][y] = min;
    return map[x][y];
}

};
```

[raof01]

这道题比较有意思，可以从左上往右下计算，也可以右下往左上计算（C++迭代）：

class Solution {
public:
    int minPathSum(vector<vector<int>>& map) {
        auto sums = vector<vector<int>>(map.size(), vector<int>(map[0].size(), INT_MAX));
        auto rows = map.size();
        auto cols = map[0].size();
    sums[rows - 1][cols - 1] = map[rows - 1][cols - 1];
    for (auto i = rows - 1; i != static_cast<size_t>(-1); --i) {
        for (auto j = cols - 1; j != static_cast<size_t>(-1); --j) {
            if (sums[i][j] != INT_MAX) continue;
            auto vr = (j == cols - 1) ?
                            INT_MAX :
                            sums[i][j + 1];
            auto vd = (i == rows - 1) ?
                            INT_MAX :
                            sums[i + 1][j];
            sums[i][j] = min(vr, vd) + map[i][j];
        }
    }
    return sums[0][0];
    }
};

[azl397985856]

这道题比较有意思，可以从左上往右下计算，也可以右下往左上计算（C++迭代）：

class Solution {
public:
    int minPathSum(vector<vector<int>>& map) {
        auto sums = vector<vector<int>>(map.size());
  for (auto i = 0; i < map.size(); ++i) {
      sums[i] = vector<int>(map[0].size(), INT_MAX);
  }
  sums[map.size() - 1][map[0].size() - 1] = map[map.size() - 1][map[0].size() - 1];
  for (auto i = map.size() - 1; i != static_cast<size_t>(-1); --i) {
      for (auto j = map[0].size() - 1; j != static_cast<size_t>(-1); --j) {
          if (sums[i][j] != INT_MAX) continue;
          auto vr = j == map[0].size() - 1 ? INT_MAX : sums[i][j + 1];
          auto vd = i == map.size() - 1 ? INT_MAX : sums[i + 1][j];
          sums[i][j] = min(vr, vd) + map[i][j];
      }
  }
  return sums[0][0];
    }
};

非常棒，不过建议格式化一下

[3460741663]

认领

[wjj31767]

python3

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        for i in range(1, m):
            grid[i][0] += grid[i - 1][0]
        for i in range(1, n):
            grid[0][i] += grid[0][i - 1]

        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += min(grid[i][j - 1], grid[i - 1][j])
        return grid[m - 1][n - 1]

[watchpoints]

~~~
/**

1. Minimum Path Sum
   Input:
   [
   [1,3,1],
   [1,5,1],
   [4,2,1]
   ]
   Output: 7
   Explanation: Because the path 1→3→1→1→1 minimizes the sum.

时间复杂度 O(M×N) ： 遍历整个 gridgrid 矩阵元素。
空间复杂度 O(1)O(1) ： 直接修改原矩阵，不使用额外空间

**/
func minPathSum(grid [][]int) int {

rows := len(grid)
if rows == 0 {
    return 0
}

cols := len(grid[0])

for i := 0; i < rows; i++ {
    for j := 0; j < cols; j++ {

        if i == 0 && j == 0 {
            continue
        }

        if i == 0 {
            grid[i][j] = grid[i][j-1] + grid[i][j]
        } else if j == 0 {
            grid[i][j] = grid[i-1][j] + grid[i][j]
        } else {
            temp := int(math.Min(float64(grid[i][j-1]), float64(grid[i-1][j])))
            grid[i][j] = temp + grid[i][j]
        }

    }
}

return grid[rows-1][cols-1]

}
~~~

[azl397985856]

https://github.com/azl397985856/leetcode/blob/master/daily/2019-08-09.md