【每日一题】- 2019-08-08 - 64.最小路径和 about leetcode HOT 7 CLOSED

/**
 * @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];
    }
};

from leetcode.

这道题比较有意思，可以从左上往右下计算，也可以右下往左上计算（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];
    }
};

from leetcode.

/**
64. 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]

}

from leetcode.

这道题比较有意思，可以从左上往右下计算，也可以右下往左上计算（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];
    }
};

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

from leetcode.

认领

from leetcode.

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]
                

from leetcode.

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

from leetcode.