力扣64——最小路径和

原题

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解法

错误的正向思路

我一开始的想法是正向思路，从起点开始，每个点都有两种后续走法——向下或者向右，当然其中需要判断是否可以向下或者向右以及到达终点就停止。我想到的优化是当走到终点后，将当前走过的路径和记录下来，找出最小值，别的路径上在走的时候，如果比当前最小和大，就没必要继续了。

来看看我的代码：

class Solution {
    private long min = Long.MAX_VALUE;

    private int[][] map;

    public int minPathSum(int[][] grid) {
        map = grid;
        dfs(0, 0, 0);
        return (int)min;
    }

    public void dfs(int x, int y, long sum) {
        sum += Long.valueOf(map[x][y]);
        // 如果已经大于等于当前的最小值，那么就没有必要继续走了
        if (sum >= min) {
            return;
        }

        // 是否到达终点
        if (x == map.length - 1 && y == map[x].length - 1) {
            if (sum < min) {
                min = sum;
            }

            return;
        }

        // 是否可以向右
        if (y < map[x].length - 1) {
            dfs(x, y + 1, sum);
        }
        // 是否可以向下
        if (x < map.length - 1) {
            dfs(x + 1, y, sum);
        }
    }
}

感觉很理想，然而现实是超时了，确实效率不高，除了第一列和第一行的点，其他点都有可能存在重复计算的可能。

逆向思路

既然正向不行，那咋们就逆向，从终点出发，以终点为起点，计算当前点到终点的最小值，最后推算出到达起点的最小值（这也是我看了别人的解法才知道的，看来自己的思路果然有问题）。这样就能保证每个点只计算一次，时间效率就是O(m * n)，看起来就高效多了。

接下来看看代码：

class Solution {
    public int minPathSum(int[][] grid) {
        // 从终点开始找起，算当前节点到终点的最小值
        int right, down;
        for (int i = grid.length - 1; i >= 0; i--) {
            for (int j = grid[i].length - 1; j >= 0; j--) {
                // 如果是终点，则保持不变
                if (i == grid.length - 1 && j == grid[i].length - 1) {
                    continue;
                }

                // 如果没有右节点
                if (j == grid[i].length - 1) {
                    // 那么就设置当前节点的值加上下节点的值
                    grid[i][j] += grid[i + 1][j];
                    continue;
                }

                // 如果没有下节点
                if (i == grid.length - 1) {
                    // 那么就设置当前节点的值加上右节点的值
                    grid[i][j] += grid[i][j + 1];
                    continue;
                }

                // 如果下节点和右节点都有的话，则加上其中较小的那个
                grid[i][j] += grid[i + 1][j] < grid[i][j + 1] ? grid[i + 1][j] : grid[i][j + 1];
            }
        }

        return grid[0][0];
    }
}

OK，通过了，执行用时： 3ms ，内存消耗： 39.5MB 。

核心思想就是：

从终点出发，每个点到终点的最小值 = 每个点当前的值 + Min(该点下一个点值, 该点右一个点)。

你想想，是否是如此呢？

既然知道了反向思路，我们可以优化一下我们之前的正向思路解法。

优化正向思路

之前的超时，是因为每个点可能会被计算多次，那么我们如果计算出，从起点出发，到每个节点的最小值，最终计算到终点，也应该是终点的最小值，你想想是不是这样呢？

来看看代码

class Solution {
    public int minPathSum(int[][] grid) {
        // 从起点开始找起，算当前节点到起点的最小值

        // 总行数
        int row = grid.length;
        // 总列数
        int col = grid[0].length;
        // 左节点和上节点计算出的最小值
        int left, up;
        // 遍历并计算
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                // 起点不计算
                if (i == 0 && j == 0) {
                    continue;
                }

                // 如果没有左节点
                if (j == 0) {
                    // 就设置当前节点的值加上节点
                    grid[i][j] += grid[i - 1][j];
                    continue;
                }

                // 如果没有上节点
                if (i == 0) {
                    // 就设置当前节点的值加上左节点
                    grid[i][j] += grid[i][j - 1];
                    continue;
                }

                // 如果左节点和上节点都存在，就加上其中最小的值
                grid[i][j] += (grid[i][j - 1] < grid[i - 1][j] ? grid[i][j - 1] : grid[i - 1][j]);
            }
        }

        return grid[row - 1][col - 1];
    }
}

OK，也通过了，执行用时： 3ms ，内存消耗： 42.4MB 。

总结

以上就是这道题目我的解答过程了，不知道大家是否理解了。算法本来就是就是在做优化，如何能比之前更好更合适，就是优化了。希望能与大家共同进步。

有兴趣的话可以访问我的博客或者关注我的公众号，说不定会有意外的惊喜。

https://death00.github.io/

公众号：健程之道

点击此处留言

PS：今天冬至，冬天开始，winter is coming ! 2019即将结束，希望大家都能完成自己曾在2019许下的愿望。