二维数组的最小路径和问题
作者：Grey
原文地址:
题目描述
LintCode 110 · Minimum Path Sum
给定一个只含非负整数的
m ∗ n网格，找到一条从左上角到右下角的可以使数字和最小的路径。
暴力解法（超时）
定义递归函数
int process(int[][] grid, int i, int j) 递归含义：从i,j开始，一直到最后，最小的路径和是多少。
主方法直接调用
// 从0，0开始，一直到最后，最小路径和是多少 process(grid,0,0) 即为答案。
base case 为:
-
当前点已经到最后一行了,只能向右走。
-
当前点已经到最后一列了,只能向下走。
如下代码:
// 到最后一行了，只能向右走 if (i == grid.length - 1) { int sum = 0; for (int m = j; m < grid[0].length; m++) { sum += grid[i][m]; } return sum; } // 到最后一列了，只能向下走 if (j == grid[0].length - 1) { int sum = 0; for (int m = i; m < grid.length; m++) { sum += grid[m][j]; } return sum; } 针对普遍位置,即可以向下走,也可以向右走,决策出最小路径即可。
// 普遍位置 int p1 = grid[i][j], p2 = grid[i][j]; if (i + 1 < grid.length) { // 向下走 p1 += process(grid, i + 1, j); } if (j + 1 < grid[0].length) { // 向右走 p2 += process(grid, i, j + 1); } return Math.min(p1, p2); 暴力解法完整代码如下
// 暴力解，超时 public static int minPathSum(int[][] grid) { if (grid == null || grid.length < 1 || grid[0].length < 1) { return 0; } return process(grid, 0, 0); } // 从i，j开始，一直到最后，最小路径和是多少 public static int process(int[][] grid, int i, int j) { // 到最后一行了，只能向右走 if (i == grid.length - 1) { int sum = 0; for (int m = j; m < grid[0].length; m++) { sum += grid[i][m]; } return sum; } // 到最后一列了，只能向下走 if (j == grid[0].length - 1) { int sum = 0; for (int m = i; m < grid.length; m++) { sum += grid[m][j]; } return sum; } // 普遍位置 int p1 = grid[i][j], p2 = grid[i][j]; if (i + 1 < grid.length) { p1 += process(grid, i + 1, j); } if (j + 1 < grid[0].length) { p2 += process(grid, i, j + 1); } return Math.min(p1, p2); } 这个解法超时。
使用缓存
由于上述暴力递归函数中,i 和 j 的变化范围有限,我们可以设置一个二维dp,保存所有i,j状态下的最优解,如果计算过,则直接返回dp[i][j]的值.
二维数组dp的初始值均为Integer.MAX_VALUE, 在递归函数中,增加这个dp变量,如果
if (dp[i][j] != Integer.MAX_VALUE) { return dp[i][j]; } 说明i,j状态下的最优解已经算过了,直接返回即可.
完整代码如下
public class Solution { /** * @param grid: a list of lists of integers * @return: An integer, minimizes the sum of all numbers along its path */ public static int minPathSum(int[][] grid) { if (grid == null || grid.length < 1 || grid[0].length < 1) { return 0; } // 缓存 int[][] dp = new int[grid.length][grid[0].length]; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { dp[i][j] = Integer.MAX_VALUE; } } return process(grid, 0, 0, dp); } // 使用缓存 public static int process(int[][] grid, int i, int j, int[][] dp) { if (dp[i][j] != Integer.MAX_VALUE) { return dp[i][j]; } // 到最后一行了，只能向右走 if (i == grid.length - 1) { int sum = 0; for (int m = j; m < grid[0].length; m++) { sum += grid[i][m]; } dp[i][j] = sum; return sum; } // 到最后一列了，只能向下走 if (j == grid[0].length - 1) { int sum = 0; for (int m = i; m < grid.length; m++) { sum += grid[m][j]; } dp[i][j] = sum; return sum; } // 普遍位置 int p1 = grid[i][j], p2 = grid[i][j]; if (i + 1 < grid.length) { p1 += process(grid, i + 1, j, dp); } if (j + 1 < grid[0].length) { p2 += process(grid, i, j + 1, dp); } dp[i][j] = Math.min(p1, p2); return dp[i][j]; } } 动态规划(二维数组)
回到暴力递归的解法,略去其他代码,伪代码如下
public static int process(int[][] grid, int i, int j) { .... // 普遍位置 ... p1 += process(grid, i + 1, j); ... ... p2 += process(grid, i, j + 1); ... return ....; } 分析这个递归过程,如果用二维dp装下这个过程,任何一个i,j位置依赖i+1,j+1位置,而最后一行和最后一列的dp值是可以预先计算出来的.
所以整个dp表的求解流程如下图
从 X 点开始,从右到左,从下到上,一直求到左上角,即0,0位置的值,dp[0][0]就是答案.
完整代码如下
public class Solution { /** * @param grid: a list of lists of integers * @return: An integer, minimizes the sum of all numbers along its path */ public static int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; dp[m - 1][n - 1] = grid[m - 1][n - 1]; for (int i = m - 2; i >= 0; i--) { dp[i][n - 1] = grid[i][n - 1] + dp[i + 1][n - 1]; } for (int i = n - 2; i >= 0; i--) { dp[m - 1][i] = grid[m - 1][i] + dp[m - 1][i + 1]; } for (int i = m - 2; i >= 0; i--) { for (int j = n - 2; j >= 0; j--) { dp[i][j] = grid[i][j] + Math.min(dp[i + 1][j], +dp[i][j + 1]); } } // 普遍位置 return dp[0][0]; } } 动态规划(压缩数组优化)
基于上述动态规划的解,我们可以将dp简化成一维数组,由于二维dp的填充方式是从右下角开始,从右到左,从下到上,所以我们可以设置一个一维数组进行滚动刷新,而不需要浪费一个二维数组的额外空间.
完整代码如下
public class Solution { /** * @param grid: a list of lists of integers * @return: An integer, minimizes the sum of all numbers along its path */ public static int minPathSum(int[][] grid) { int m = grid.length; int n = grid[0].length; // int[] dp = new int[n]; // 最右下角位置 dp[n - 1] = grid[m - 1][n - 1]; // 填最后一行 for (int i = n - 2; i >= 0; i--) { dp[i] = dp[i + 1] + grid[m - 1][i]; } int first = dp[n - 1]; for (int i = m - 2; i >= 0; i--) { dp[n - 1] = first + grid[i][n - 1]; for (int j = n - 2; j >= 0; j--) { dp[j] = grid[i][j] + Math.min(dp[j], dp[j + 1]); } first = dp[n - 1]; } // 普遍位置 return dp[0]; } } 
