题目描述
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
代码
class Solution {
public int minPathSum(int[][] grid) {
int n = grid.length, m = grid[0].length;
int[][] f = new int[n+5][m+5];
f[0][0] = grid[0][0];
for(int i=1; i<m; i++) f[0][i] = f[0][i-1]+grid[0][i];
for(int i=1; i<n; i++) f[i][0] = f[i-1][0]+grid[i][0];
for(int i=1; i<n; i++){
for(int j=1; j<m; j++){
f[i][j] = Math.min(f[i-1][j], f[i][j-1])+grid[i][j];
}
}
return f[n-1][m-1];
}
}