LeetCode-64. 最小路径和

题目来源
64. 最小路径和

动态规划

• 1.确定dp数组以及下标的含义

定义 dp[i][j] 为从 (0,0) 开始到达位置 (i,j) 的最小总和。

• 2.确定递推公式

由于题目限定了我们只能 往下 或者 往右 移动，因此我们按照当前位置可由哪些位置转移过来进行分析：
当前位置只能通过 往下 移动而来，即有 dp[i][j] = dp[i-1][j] + grid[i][j]
当前位置只能通过 往右 移动而来，即有 dp[i][j] = dp[i][j-1] + grid[i][j]
当前位置既能通过 往下 也能 往右 移动，即有 dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + grid[i][j]

• 3.dp数组如何初始化

dp 初始化即可，不需要修改初始 0 值。
这道题其实也可以初始化dp[0][j]和dp[i][0]，这样很麻烦，直接在遍历的是初始化即可

• 4.确定遍历顺序

从递归公式 dp[i][j] = Math.min(dp[i][j-1],dp[i-1][j]) + grid[i][j]中可以看出，遍历的顺序一定是从上到下，从左到右遍历

• 5.举例推导dp数组

以grid = [[1,3,1],[1,5,1],[4,2,1]]为例

代码实现

class Solution {public int minPathSum(int[][] grid) {int[][] dp = new int[grid.length][grid[0].length];dp[0][0] = grid[0][0];for(int i = 0;i<grid.length;i++){for(int j = 0;j<grid[0].length;j++){if(i == 0 && j == 0){dp[i][j] = grid[0][0];}else if(i == 0){dp[i][j] = dp[i][j-1]+grid[i][j];}else if(j == 0){dp[i][j] = dp[i-1][j]+grid[i][j];}else{dp[i][j] += Math.min(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);}}}return dp[grid.length-1][dp[0].length-1];}
}