dp-leetcode64

Leetcode-64

思路:动态规划

最短距离:

1
2
3
dp[i][j] 指的是到达i,j 时的最短路径,取决于grid[i-1][j]、grid[i][j-1] 的加和
状态方程为:
dp[i][j]=Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);

一道最简单的动态规划题,没有进行压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int minPathSum(int[][] grid) {
int width=grid[0].length; //宽度
int height=grid.length; //高度
int [][] dp=new int[height][width]; //表示走到dp[i][j] 所用的最小路径和
//初始化dp数组,其实就是处理边界的数组
dp[0][0]=grid[0][0];
for (int i = 1; i <width ; i++) {
dp[0][i]=dp[0][i-1]+grid[0][i];
}
//特殊情况处理
if (grid.length<2) return dp[0][width-1];
for (int i = 1; i <height ; i++) {
dp[i][0]=dp[i-1][0]+grid[i][0];
}
for(int i=1;i<height;i++){
for(int j=1;j<width;j++){
dp[i][j]=Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]); //状态转换方程
}
}
return dp[height-1][width-1];
}