1. 首页
  2. Leetcode经典148题

leetCode-64-Minimum-PathSum

题目描述(中等难度)

leetCode-64-Minimum-PathSum

依旧是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 题的话,很快就写出来了。

作者:windliang

来源:https://windliang.cc

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:leetCode-64-Minimum-PathSum

链接:https://www.javajike.com/article/3201.html

« leetCode-63-Unique-PathsII
leetCode-65-Valid-Number»

相关推荐

QR code