题目链接

最小路径和

题目描述

注意

• 需要找的是从左上角到右下角的路径
• 该网格是一个矩阵
• 每个格子中的数都为非负数
• 每次只能向下或者向右移动一步

解答思路

• 采用dfs + 记忆，深度优先遍历探索每个点到终点的最小路径和，如果某个点到终点的最小路径和还没有算出，则分别计算其向右和向下走的最小路径和，取最小值加上该点的值为该点到终点的最小路径和。如此便可推出每个点到终点的最小路径和

代码

class Solution {
    private int[][] memo;
    // 行数
    private int M;
    // 列数
    private int N;

    public int minPathSum(int[][] grid) {
        M = grid.length;
        N = grid[0].length;

        // 初始化记忆数组，填充值为-1       
        memo = new int[M][N];
        for (int i = 0; i < M; i++) {
            Arrays.fill(memo[i], -1);
        }
        int res = dfs(grid, 0, 0);
        return res;
    }

    // 深度优先遍历，该方法返回的是从坐标为(x,y)的点触发到右下角的最小路径和
    private int dfs(int[][] grid, int r, int c) {
        // 若越界，则认为不可达，距离为无穷大
        if (r < 0 || r >= M || c < 0 || c >= N) {
            return Integer.MAX_VALUE;
        }

        // 若该格子已经记录最小路径和，则直接返回
        if (memo[r][c] > -1) {
            return memo[r][c];
        }

        // 若到达终点，终点的贡献值是其本身
        if (r == M - 1 && c== N - 1) {
            return grid[M - 1][N - 1];
        }

        // 右边的点到终点的最短路径
        int right = dfs(grid, r, c + 1);

        // 下面的点到终点的最短路径
        int down = dfs(grid, r + 1, c);

        // 取两者的较小值，计算出当前点的最小路径值
        int ans = Math.min(right, down) + grid[r][c];
        memo[r][c] = ans;
        return ans;
    }
}

关键点

• 在对每个点计算其到终点的最小路径和之前，要先判断其是否越界，越界则返回无穷大
• 需要用一个记忆数组存储每个点到终点的最小路径和，如果已经算过，则直接返回记忆数组对应的值，如果没有记忆数组，则每个点都有可能被访问到多次，需要计算多次其最小路径和，时间将会大幅增加