二維陣列的最小路徑和問題

作者：Grey

原文地址:

部落格園: 二維陣列的最小路徑和問題

CSDN: 二維陣列的最小路徑和問題

題目描述

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 為:

1. 當前點已經到最後一行了,只能向右走。

2. 當前點已經到最後一列了,只能向下走。

如下程式碼:

// 到最後一行了，只能向右走
        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];
    }
}

更多

演演算法和資料結構筆記