矩形最小路径和 · Minimum Path Sum

［抄题］：

给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。

［思维问题］：

［一句话思路］：

和数字三角形基本相同

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

行、列的数字是不一样的，要分开算

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

原点的初始距离是它本身，而不是0。因为点本身就有距离

［复杂度］：Time complexity: O(n^2) Space complexity: O(n^2)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

DP，最短最值。朝着4个方向走时，无法比较距离的大小关系，不能用dp

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

62. Unique Paths 去右下角-dp

174. Dungeon Game 去右下角-dp

741. Cherry Pickup 去右下角-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 int minPathSum(int[][] grid) {

        //corner case

        if (grid == null || grid.length == 0) {

            return -1;

        }

        if (grid[0] == null || grid[0].length == 0) {

            return -1;

        }

        //intialization

        int m = grid.length;

        int n = grid[0].length;

        int[][] f = new int[m][n];

        f[0][0] = grid[0][0];//

        for (int i = 1; i < m; i++) {

            f[i][0] = f[i - 1][0] + grid[i][0];

        }

        for (int j = 1; j < n; j++) {

            f[0][j] = f[0][j - 1] + grid[0][j];

        }

        //top down

        for (int i = 1; i < m; i++) {

            for (int j = 1; j < n; j++) {

                f[i][j] = grid[i][j] + Math.min(f[i - 1][j],f[i][j - 1]);

            }

        }

        //result

        return f[m - 1][n - 1];

    }

}

巴特西

矩形最小路径和 · Minimum Path Sum

最新文章

热门文章