二維數組的最小路徑和問題
二維數組的最小路徑和問題
作者：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];
}
}
