题目描述:题目链接
同样对于这个问题,我们可以考虑用动态规划来解决。
解决动态规划常见的三个步骤:
1:问题的归纳。对于 i,j 位置上的最短路径可以用d[ i ][ j ]表示。
2:归纳递推式:d[ i ][ j ] = Math.min( d [ i - 1 ] [ j ] , d [ i ] [ j - 1 ] ) + grid[ i ][ j ];因为题目中规定,只能向下或者向右边移动。
3:初始化d. 对于首行和首列肯定可以用一个for循环来表示。
要点:我们可以借用原数组来表示d,而不需要重新再new一个数组。
下面给出代码的描述:
class Solution {
public int minPathSum(int[][] grid) {
//利用动态规划思路解决
//先初始化首列
for(int i = 1; i < grid.length;i++)
grid[i][0] += grid[i-1][0];
//初始化首行
for(int i = 1; i < grid[0].length; i++)
grid[0][i] += grid[0][i-1] ; for(int i = 1; i < grid.length; i++){
for(int j = 1; j < grid[0].length;j++){
grid[i][j] = Math.min(grid[i][j-1],grid[i-1][j])+grid[i][j];
}
}
return grid[grid.length-1][grid[0].length-1];
}
}