MENU

LeetCode64. Minimum Path Sum(动态规划)

2019 年 03 月 24 日 • 阅读: 1090 • LeetCode阅读设置

LeetCode64. Minimum Path Sum(动态规划)

  • Medium
  • Accepted:215,048
  • Submissions:468,498

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

链接

https://leetcode.com/problems/minimum-path-sum

题意

给定一个m * n的网格,其中均为非负整数,找到一条从左上角到右下角的路径,满足路径上的数字和最小,每次可以向右或向下移动。

题解

考虑一下我们之前做的三角形的路径最小值:LeetCode120. Triangle(动态规划),有些类似。

根据题目规则,每次可以向右或向下移动,也就是对于当前的数字,可以从它上边的数字和它左边的数字走到它。

假设$dp[i][j]$表示从左上角走到第i列第j行时路径的最小和,那么递推方程为:$dp[i][j] = dp[i-1][j] + dp[i][j-1]+dp[i][j]$。

注意边界条件,当 i = 0 或 j = 0时,数组下标会超范围,所以需要单独判断,或者在递推之前做个预处理,然后i和j都从1开始。

平均时间复杂度$O(nm)$,在改变原数组的情况下额外空间为$O(1)$。

代码

  • Runtime: 12 ms, faster than 99.16% of C++ online submissions for Minimum Path Sum.
  • Memory Usage: 10.9 MB, less than 79.87% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (i == 0 && j == 0)
                    grid[i][j] = grid[i][j];
                else if (i == 0 && j != 0)
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                else if (i != 0 && j == 0)
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                else
                    grid[i][j] = min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
            }
        }
        return grid[n - 1][m - 1];
    }
};
  • Runtime: 12 ms, faster than 99.16% of C++ online submissions for Minimum Path Sum.
  • Memory Usage: 10.7 MB, less than 98.11% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        for (int i = 1; i < n; ++i)
            grid[i][0] = grid[i - 1][0] + grid[i][0];
        for (int j = 1; j < m; ++j)
            grid[0][j] = grid[0][j - 1] + grid[0][j];
        for (int i = 1; i < n; ++i)
            for (int j = 1; j < m; ++j)
                grid[i][j] = min(grid[i][j - 1], grid[i - 1][j]) + grid[i][j];
        return grid[n - 1][m - 1];
    }
};

事实上我这种写法“不规范”,因为我是在原数组上直接操作的,改变了原数组的值,我们应该再开一个新的二维数组,但是这样的话空间复杂度就会是$O(nm)$,实际上$dp[i][j]$,只它左边的数$dp[i][j-1]$(左列)和上边的数$dp[i-1][j]$(当前列)相关,所以我们只需要用一个数组来维护。

比如我们按行来进行遍历,那么我们需要一个数组cur保存当前行的最左边1个数和上边一行n-1个数的信息。对于样例,$cur[0]_{1, 0} = 1+1 = 2$(处理边界),$cur[1]_{0, 1} = 3 + 1 = 4$,$cur[2]_{0, 2} = 1 + 4 = 5$。然后开始更新,$cur[1]_{1, 1} = max(cur[0]_{1, 0}, cur[1]_{0, 1}) + grid[1][1]$,"5"由左“1”和上“3”更新,具体参考代码。

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
  • Runtime: 16 ms, faster than 23.50% of C++ online submissions for Minimum Path Sum.
  • Memory Usage: 10.8 MB, less than 94.65% of C++ online submissions for Minimum Path Sum.
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector <int> cur(m, grid[0][0]);
        for (int i = 1; i < m; ++i)
            cur[i] = cur[i - 1] + grid[0][i];
        for (int i = 1; i < n; ++i)
        {
            cur[0] += grid[i][0];
            for (int j = 1; j < m; ++j)
                cur[j] = min(cur[j - 1], cur[j]) + grid[i][j];
        }
        return cur[m - 1];
    }
};

参考


The end.
2019年3月24日 星期日
最后编辑于: 2019 年 03 月 25 日