来源Leetcode第64题最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
二维动态规划
采用一个二维数组dp[][]来标记到右下角时的最小路径。
则dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + arr[i][j],意为到第(i,j)个格子的最短路径等于从上方或者左边的格子的最短路径 加上 到当前格子所需的路径
这样的话只需对dp[][]做初始化即可。
最开始dp[0][0] = arr[0][0],作为左上角格子走的步数，接下来初始化第一行，第一行等于从左边走的路径加上arr[0][i],即 dp[0][i] = dp[0][i - 1] + grid[0][i]
同理初始化第一列为 dp[i][0] = dp[i-1][0] + grid[i][0];
这样的话写出的代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
if(row == 0 || col == 0)
return 0;
int [][] dp = new int[row][col];
dp[0][0] = grid[0][0];
for(int i = 1;i < row;i++)
dp[i][0] = dp[i-1][0] + grid[i][0];
for(int i = 1;i < col ; i++)
dp[0][i] = dp[0][i - 1] + grid[0][i];
for(int i = 1 ; i < row; i++)
for(int j = 1 ; j< col ; j++)
dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
return dp[row - 1][col - 1];
}
一维动态规划
来源题解
在上个解法中，我们可以用一个一维数组来代替二维数组，dp数组的大小和行大小相同。这是因为对于某个固定状态，只需要考虑下方和右侧的节点。首先初始化 dp数组最后一个元素是右下角的元素值，然后我们向左移更新每个 dp(j) 为：
dp[j] - min(dp[j],dp[j+1]) + arr[i][j]
我们对于每一行都重复这个过程，然后向上一行移动，计算完成后 dp(0) 就是最后的结果。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public int minPathSum(int[][] grid) {
int[] dp = new int[grid[0].length];
for (int i = grid.length - 1; i >= 0; i--) {
for (int j = grid[0].length - 1; j >= 0; j--) {
if(i == grid.length - 1 && j != grid[0].length - 1)
//在最后一行的其他列，来自右边的路径
dp[j] = grid[i][j] + dp[j + 1];
else if(j == grid[0].length - 1 && i != grid.length - 1)
//上移到上一行
dp[j] = grid[i][j] + dp[j];
else if(j != grid[0].length - 1 && i != grid.length - 1)
//左移
dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]);
else
dp[j] = grid[i][j];
}
}
return dp[0];
}
不用任何额外存储空间的动态规划
同二维一致，不过是在原数组上存储，grid[i][j] = grid[i][j] + mid(grid[i-1][j],grid[i][j-1])
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15public int minPathSum(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
for(int i = 0 ;i < row ; i++)
for(int j = 0 ; j < col ; j++){
if(i == 0 && j != 0)
grid[i][j] = grid[i][j] + grid[i][j - 1];
else if(j == 0 && i != 0)
grid[i][j] = grid[i][j] + grid[i - 1][j];
else if(j != 0 && i != 0)
grid[i][j] = grid[i][j] + Math.min(grid[i][j - 1], grid[i - 1][j]);
}
return grid[row - 1][col - 1];
}