64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

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

My Solution(C/C++)

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minPathSum(vector<vector<int>> &grid) {
        vector<vector<int>> dp(grid.size(), vector<int>());
        dp[0].push_back(grid[0][0]);
        for (int row = 0; row < grid.size(); row++) {
            for (int column = 0; column < grid[row].size(); column++) {
                if (row == 0 && column != 0) {
                    dp[row].push_back(dp[row][column - 1] + grid[row][column]);
                }
                else if (row != 0 && column == 0) {
                    dp[row].push_back(dp[row - 1][column] + grid[row][column]);
                }
                else if(row != 0 && column != 0){
                    dp[row].push_back(min(dp[row][column - 1], dp[row - 1][column]) + grid[row][column]);
                }
            }
        }
        return dp[grid.size() - 1][grid[grid.size() - 1].size() - 1];
    }
};

int main() {
    vector<vector<int>> grid(3, vector<int>());
    grid[0].push_back(1);
    grid[0].push_back(3);
    grid[0].push_back(1);
    grid[1].push_back(1);
    grid[1].push_back(5);
    grid[1].push_back(1);
    grid[2].push_back(4);
    grid[2].push_back(2);
    grid[2].push_back(1);
    Solution s;
    printf("矩形最小路径和：%d", s.minPathSum(grid));
    return 0;
}

结果

矩形最小路径和：7

My Solution(Python)

class Solution:
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if grid == []:
            return 0
        row = len(grid)
        column = len(grid[0])
        dp = [[-1 for i in range(column)] for j in range(row)]
        dp[0][0] = grid[0][0]
        for i in range(1, row):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, column):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        for i in range(1, row):
            for j in range(1, column):
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        return dp[-1][-1]