题目描述（中等难度）

依旧是62题的扩展，这个是输出从左上角到右下角，路径的数字加起来和最小是多少。

依旧在62题代码的基础上改，大家可以先看下 62 題。

解法一 递归

62 题中我们把递归 getAns 定义为，输出 （x，y）到 （m ，n ） 的路径数，如果记做 dp[x][y]。

那么递推式就是 dp[x][y] = dp[x][y+1] + dp[x+1][y]。

这道题的话，把递归 getAns 定义为，输出 （x，y）到 （m，n ） 的路径和最小是多少。同样如果记做 dp[x][y]。这样的话， dp[x][y] = Min（dp[x][y+1] + dp[x+1][y]）+ grid[x][y]。很好理解，就是当前点的右边和下边取一个和较小的，然后加上当前点的权值。

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    HashMap<String, Integer> visited = new HashMap<>();
    return getAns(0, 0, m - 1, n - 1, 0, visited, grid);
}
private int getAns(int x, int y, int m, int n, int num, HashMap<String, Integer> visited, int[][] grid) {
    // 到了终点，返回终点的权值
    if (x == m && y == n) {
        return grid[m][n];
    }
    int n1 = Integer.MAX_VALUE;
    int n2 = Integer.MAX_VALUE;
    String key = x + 1 + "@" + y;
    if (!visited.containsKey(key)) {
        if (x + 1 <= m) {
            n1 = getAns(x + 1, y, m, n, num, visited, grid);
        }
    } else {
        n1 = visited.get(key);
    }
    key = x + "@" + (y + 1);
    if (!visited.containsKey(key)) {
        if (y + 1 <= n) {
            n2 = getAns(x, y + 1, m, n, num, visited, grid);
        }
    } else {
        n2 = visited.get(key);
    }
    // 将当前点加入 visited 中
    key = x + "@" + y;
    visited.put(key, Math.min(n1, n2) + grid[x][y]);
    //返回两个之间较小的，并且加上当前权值
    return Math.min(n1, n2) + grid[x][y];
}

时间复杂度：

空间复杂度：

解法二

这里我们直接用 grid 覆盖存，不去 new 一个 n 的空间了。

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    //由于第一行和第一列不能用我们的递推式，所以单独更新
    //更新第一行的权值
    for (int i = 1; i < n; i++) {
        grid[0][i] = grid[0][i - 1] + grid[0][i];
    }
    //更新第一列的权值
    for (int i = 1; i < m; i++) {
        grid[i][0] = grid[i - 1][0] + grid[i][0];
    }
    //利用递推式更新其它的
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] = Math.min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
        }
    }
    return grid[m - 1][n - 1];
}

时间复杂度：O（m * n）。

空间复杂度：O（1）。

总

依旧是62题的扩展，理解了 62 题的话，很快就写出来了。

添加好友一起进步~

如果觉得有帮助的话，可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情