【leetcode刷题】T158-最小路径和

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

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        # 二维：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        # 一维：dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
        if not grid or not grid[0]:
            return 0
        dp = [sys.maxsize] * len(grid[0])
        dp[0] = 0

        for i in range(len(grid)):
            dp[0] += grid[i][0]
            for j in range(1, len(grid[0])):
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j]

        return dp[-1]

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        // 二维：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        // 一维：dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
        if(grid.size() == 0 || grid[0].size() == 0)
            return 0;
        vector<int> dp(grid[0].size(), INT_MAX);
        dp[0] = 0;
        for(int i=0; i < grid.size(); i++){
            dp[0] += grid[i][0];
            for(int j=1; j < grid[0].size(); j++){
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j];
            }
        }
        return dp.back();
    }
};