LeetCode 64. Minimum Path Sum

思路

动态规划的问题，某一格的状态由它左侧及上侧的状态决定，即
[latex]minVal[x][y] = min( minVal[x-1][y], minVal[x][y-1] )[/latex]
当然了，第一行只由左侧决定，第一列只由上侧决定。

代码

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