When the world turns its back on you, you turn your back on the world! And only embrace what's next!
若世界与你背道而驰,你无需亦步亦趋,欣然走好接下来的每一步吧! 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。 说明:每次只能向下或者向右移动一步。 示例: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
这题求的是从左上角到右下角,路径上的数字和最小,并且每次只能向下或向右移动。所以上面很容易想到动态规划求解。我们可以使用一个二维数组dp,dp[i][j]表示的是从左上角到坐标(i,j)的最小路径和。那么走到坐标(i,j)的位置只有这两种可能,要么从上面(i-1,j)走下来,要么从左边(i,j-1)走过来,我们要选择路径和最小的再加上当前坐标的值就是到坐标(i,j)的最小路径。 所以递推公式就是
dp[i][j]=min(dp[i-1][j]+dp[i][j-1])+grid[i][j]; 有了递推公式再来看一下边界条件,当在第一行的时候,因为不能从上面走下来,所以当前值就是前面的累加。同理第一列也一样,因为他不能从左边走过来,所以当前值只能是上面的累加。 比如上面图中,如果我们走到中间这一步的话,我们可以从上面1→3→5走过来,也可以从左边1→1→5,我们取最小的即可。我们来看下代码
1public int minPathSum(int[][] grid) { 2 int m = grid.length, n = grid[0].length; 3 int[][] dp = new int[m][n]; 4 dp[0][0] = grid[0][0]; 5 //第一列只能从上面走下来 6 for (int i = 1; i < m; i++) { 7 dp[i][0] = dp[i - 1][0] + grid[i][0]; 8 } 9 //第一行只能从左边走过来 10 for (int i = 1; i < n; i++) { 11 dp[0][i] = dp[0][i - 1] + grid[0][i]; 12 } 13 for (int i = 1; i < m; i++) { 14 for (int j = 1; j < n; j++) { 15 //递推公式,取从上面走下来和从左边走过来的最小值+当前坐标的值 16 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; 17 } 18 } 19 return dp[m - 1][n - 1]; 20} 21
我们看到二维数组dp和二维数组grid的长和宽都是一样的,没必要再申请一个dp数组,完全可以使用grid,来看下代码
1public int minPathSum(int[][] grid) { 2 int m = grid.length, n = grid[0].length; 3 for (int i = 0; i < m; i++) { 4 for (int j = 0; j < n; j++) { 5 if (i == 0 && j == 0) 6 continue; 7 if (i == 0) { 8 //第一行只能从左边走过来 9 grid[i][j] += grid[i][j - 1]; 10 } else if (j == 0) { 11 //第一列只能从上面走下来 12 grid[i][j] += grid[i - 1][j]; 13 } else { 14 //递推公式,取从上面走下来和从左边走过来的最小值+当前坐标的值 15 grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]); 16 } 17 } 18 } 19 return grid[m - 1][n - 1]; 20}
我们还可以把上面的动态规划改为递归,定义一个函数 minPathSum(int[][] grid, int i, int j)表示从左上角到坐标(i,j)的最短路径和,那么同样道理,要走到坐标(i,j)只能从上面下来或者左边过来。所以代码轮廓我们大致能写出来 1public int minPathSum(int[][] grid, int i, int j) { 2 if (边界条件的判断) { 3 return 4 } 5 6 //一些逻辑处理 7 8 //取从上面走下来和从左边走过来的最小值+当前坐标的值 9 return grid[i][j] + Math.min(minPathSum(grid, i - 1, j), minPathSum(grid, i, j - 1)); 10}
下面再来看下完整代码 1public int minPathSum(int[][] grid) { 2 return minPathSum(grid, grid.length - 1, grid[0].length - 1); 3} 4 5public int minPathSum(int[][] grid, int i, int j) { 6 if (i == 0 && j == 0) 7 return grid[i][j]; 8 //第一行只能从左边走过来 9 if (i == 0) 10 return grid[i][j] + minPathSum(grid, i, j - 1); 11 //第一列只能从上面走下来 12 if (j == 0) 13 return grid[i][j] + minPathSum(grid, i - 1, j); 14 //取从上面走下来和从左边走过来的最小值+当前坐标的值 15 return grid[i][j] + Math.min(minPathSum(grid, i - 1, j), minPathSum(grid, i, j - 1)); 16}
因为这里面的递归会导致大量的重复计算,所以还是老方法,就是把计算过的值存储到一个map中,下次计算的时候先看map中是否有,如果有就直接从map中取,如果没有再计算,计算之后再把结果放到map中,来看下代码 1public int minPathSum(int[][] grid) { 2 return minPathSum(grid, grid.length - 1, grid[0].length - 1, new HashMap<String, Integer>()); 3} 4 5public int minPathSum(int[][] grid, int i, int j, Map<String, Integer> map) { 6 if (i == 0 && j == 0) 7 return grid[i][j]; 8 String key = i + "*" + j; 9 if (map.containsKey(key)) 10 return map.get(key); 11 int res = 0; 12 //第一行只能从左边走过来 13 if (i == 0) 14 res = grid[i][j] + minPathSum(grid, i, j - 1, map); 15 //第一列只能从上面走下来 16 else if (j == 0) 17 res = grid[i][j] + minPathSum(grid, i - 1, j, map); 18 //取从上面走下来和从左边走过来的最小值+当前坐标的值 19 else 20 res = grid[i][j] + Math.min(minPathSum(grid, i - 1, j, map), minPathSum(grid, i, j - 1, map)); 21 map.put(key, res); 22 return res; 23}
|