2021/1/28 矩阵的最小路径和

题目描述

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

示例

输入

[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]

返回值

12

解题思路

解法与《2021/1/25 求路径》 以及《2021/1/21 藏宝图》类似。

1. 很经典的动态规划问题，将大问题划分为多个子问题，每个子问题的任务也是求当前路径的最小路径和。
2. 假设矩阵 arr 规模为 1 x 1，那么最小路径和就是 arr[0][0]；假设规模为 2 x 2，那么 arr[0][1] 的最小路径和就是 arr[0][0] 加上它本身的值， arr[1][0] 的最小路径和也是如此，在 arr[0][1] 和　arr[1][0] 中选取最小值，再加上 arr[0][0] 本身的值，就是当前 2 x 2 规模的最小路径和。
3. 得出结论，由于只能往下和往右走，所以第一行每格的最小路径和都等于左边一格的最小路径和加上当前数字，第一列每格的最小路径和都等于上边一格的最小路径和加上当前数字。而除此之外的格子，在其左边和上边的格子选一个路径和最小的值再加上本身值，就得出这个格子的最小路径和。遍历到数组末尾，得出最终结果。

Java代码实现

public class Solution {
    // 1. 使用二维数组实现
    public int minPathSum (int[][] matrix) {
        int rowLen  = matrix.length;
        int colLen = matrix[0].length;
        // 这里有个很小的坑，行的个数和列的个数不一样，不要被示例迷惑了
        int[][] dp = new int[rowLen][colLen];
        // 初始化第一行和第一列
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < rowLen; ++i) {
            dp[i][0] = matrix[i][0] + dp[i-1][0];
        }

        for (int i = 1; i < colLen; ++i) {
            dp[0][i] = matrix[0][i] + dp[0][i-1];
        }
        // 求每格的最小路径和
        for (int i = 1; i < rowLen; ++i) {
            for (int j = 1; j < colLen; ++j) {
                int minVal =  dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
                dp[i][j] = matrix[i][j] + minVal;
            }
        }
        return dp[rowLen - 1][colLen - 1];
    }

    // 2. 使用一维数组实现
    public int minPathSum (int[][] matrix) {
        int colLen = matrix[0].length;
        int[] dp = new int[colLen];
        dp[0] = matrix[0][0];
        for (int i = 1; i < colLen; ++i) {
            dp[i] = matrix[0][i] + dp[i-1];
        }
        for (int i = 1; i < matrix.length; ++i) {
            dp[0] += matrix[i][0];
            for (int j = 1; j < colLen; ++j) {
                int minVal =  dp[j] < dp[j-1] ? dp[j] : dp[j-1];
                dp[j] = matrix[i][j] + minVal;
            }
        }
        return dp[colLen - 1];
    }
}