LeetCode64 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.
解析：
给定一个m*n的矩阵，每个位置为非负的数值，在任一位置只能向下或者向右移动，计算所有路径中数值之和最小的数值。
此题目类似于LeetCode 62 Unique Paths
也采用动态规划来做，定义二维数组dp，dp[i][j]表示在位置i,j处路径最小值之和，因为每个位置只能向下或者向右移动，则递推公式为dp[i][j] = min(dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])。具体代码如下：

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

运行结果：
</m;></vector</vector