二维数组的最小路径和问题
作者：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];
}
}