最小路径和(Java)
一、题目描述
给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
二、思路讲解
2.1、暴力搜索(超时)
看到二维数组的题,我会先考虑能不能暴力搜索,思路是找自己右方和下方更小的那条路。
class Solution {
int [][]grid;
public int minPathSum(int[][] grid) {
this.grid = grid;
return dfs(0, 0);
}
int dfs(int i, int j) {
if(i==grid.length-1 && j==grid[0].length-1) {
return grid[i][j];
}
if(i==grid.length-1) {
return dfs(i, j+1) + grid[i][j];
}
if(j==grid[0].length-1) {
return dfs(i+1, j) + grid[i][j];
}
return Math.min(dfs(i, j+1), dfs(i+1, j)) + grid[i][j];
}
}
2.2、动态规划(二维dp数组)
既然dfs行不通,那我们就试试dp。不难看出,走到每个位置的路径和取决于他上方的格子的路径和 or 左方格子的路径和,因此我们用dp[ i ][ j ]来表示走到(i,j)位置的最小路径和,易得递推公式:dp[i][j] = min{ dp[i-1][j] , dp[i][j-1] } + grid[i][j]
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int [][]dp = new int[m][n];
dp[0][0] = grid[0][0];
for(int i=1; i<m; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i=1; i<n; i++) {
dp[0][i] = dp[0][i-1] + grid[0][i];
}
for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}
2.3、动态规划(一维dp数组)
接下来我们就来思考如何优化空间。画图可得,我们在动态规划时,是按照一行一行逐步dp的,下一行的值只由上一行和当前行决定,所以我们可以只保留上一行的数据,这样只需要用到一维数组。
这样的优化思路可参考:告别动态规划,连刷 40 道题,我总结了这些套路,看不懂你打我(万字长文) - 知乎
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int []dp = new int[n];
dp[0] = grid[0][0];
for(int i=1; i<n; i++) {
dp[i] = dp[i-1] + grid[0][i];
}
for(int i=1; i<m; i++) {
dp[0] = dp[0] + grid[i][0];
for(int j=1; j<n; j++) {
dp[j] = Math.min(dp[j-1], dp[j]) + grid[i][j];
}
}
return dp[n-1];
}
}
2.4、动态规划(不使用额外空间)
接2.2的思路,我们其实可以在原数组上直接修改,这样就不使用额外空间了。不过面试的时候有可能会要求不能更改原数组,这种情况下2.3是最优的思路。
- 点赞
- 收藏
- 关注作者
评论(0)