LeetCode 64. 最小路徑和
給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格椿访，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小阁最。
說明：每次只能向下或者向右移動(dòng)一步戒祠。
示例:
輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因?yàn)槁窂?1→3→1→1→1 的總和最小。
我的答案：
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid[0].size();
int n = grid.size();
for(int i=1;i<m;i++) grid[0][i] += grid[0][i-1];
for(int i=1;i<n;i++) grid[i][0] += grid[i-1][0];
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
grid[i][j] += grid[i-1][j] < grid[i][j-1] ? grid[i-1][j] : grid[i][j-1];
}
}
return grid[n-1][m-1];
}
};
