LeetCode 64. Minimum Path Sum    原题链接    中等

作者： 作者的头像   cornerCao ,  2018-03-27 23:21:10 ,  所有人可见 ,  阅读 1878

1


题目描述

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

样例

输入：网格矩阵
[[1,3,1],
 [1,5,1],
 [4,2,1]]
输出：7
解释：路线1→3→1→1→1，路径和最小，为7

算法

(动态规划) $O(mn)$

经典的动态规划题，用dp[i][j]记录到达网格grid[i][j]位置经过的最小的路径和，转移方程为dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])。

C++ 代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        if(m == 0)
            return 0;
        int n = grid[0].size();
        if(n == 0)
            return 0;
        vector<vector<int> > dp(m, vector<int>(n, 0));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i > 0){
                    dp[i][j] = dp[i-1][j];
                }
                if(j > 0){
                    if(i == 0)
                        dp[i][j] = dp[i][j-1];
                    else
                        dp[i][j] = min(dp[i][j], dp[i][j-1]);
                }
                dp[i][j] += grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

5 评论

用户头像
yxc   2018-03-27 23:30         踩      回复

棒！

用户头像
funny   2019-12-06 07:07         踩      回复

Y总，这题如果是求所有路径的话，解的方式是先求最小值，然后再dfs找路径么？有没有类似的题呀，感谢回答！

用户头像
yxc   2019-12-07 22:32    回复了 funny 的评论         踩      回复

这道题目类似：LeetCode 126. Word Ladder II 。

用户头像
funny   2019-12-11 07:40    回复了 yxc 的评论         踩      回复

感谢 Y总指导，自己写了一下！

public Node dfs(Map<Integer, Node> dp, int i, int j, int[][] grid) {
    // dp避免重复
    if (dp.containsKey(i * grid.length + j)) return dp.get(i * grid.length + j);
    // base case
    if (i == grid.length || j == grid[0].length) {
        return new Node(Integer.MAX_VALUE);
    }
    // leaf, 把叶子加到node的path中去
    if (i == grid.length - 1 && j == grid.length - 1) {
        Node node = new Node(grid[i][j]);
        List<int[]> list = new ArrayList<>();
        list.add(new int[]{i, j});
        node.path.add(list);
        return node;
    }

    Node child1 = dfs(dp, i + 1, j, grid);
    Node child2 = dfs(dp, i, j + 1, grid);
    int min = grid[i][j];
    Node cur = new Node(min);

    // 在当前，拿最小sum的路径，把自己加到所有path上
    if (child1.val >= child2.val) {
        cur.val += child2.val;
        for (List<int[]> list : child2.path) {
            List<int[]> tmp = new ArrayList<>(list);
            tmp.add(new int[]{i, j});
            cur.path.add(tmp);
        }
    }

    if (child1.val <= child2.val) {
        if (child1.val != child2.val)
            cur.val += child1.val;
        for (List<int[]> list : child1.path) {
            List<int[]> tmp = new ArrayList<>(list);
            tmp.add(new int[]{i, j});
            cur.path.add(tmp);
        }
    }
    return cur;
}

class Node {
int val;
List<List<int[]>> path;
public Node(int val) {
    this.val = val;
    path = new ArrayList<>();
}
用户头像
yxc   2019-12-17 00:00    回复了 funny 的评论         踩      回复

很棒！