矩阵的最小路径和

一、题目

给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

leetcode：https://leetcode.cn/problems/minimum-path-sum/

类似题目，不同路径：https://leetcode.cn/problems/unique-paths/

二、思路

典型的动态规划类题目，最终要走到右下角，这个矩阵长为 m，宽为 n。右下角为 [m-1, n-1] 位置，每一次只能走一步，那就要不是 [m-2, n-1] 走过来的，要不就是 [m-1, n-2] 走过来的，所以 [m-1, n-1] 的值应该为 std::min(arr[m-2, n-1], arr[m-1, n-2]) + 1。因此我们每一步需要选择最小的路径来走就好了。

第一行和第一列只能横着走，或者只能竖着走。所以只能填充原始数组即可。所以我们还是申请的是和原二维数组一样大小的数组，并且填充第一行和第一列。其他行和列，每次取最小路径即可。

三、code

class Solution {
public:
    int minPathSum(std::vector<std::vector<int>>& grid) {
        if (grid.empty()) {
            return 0;
        }
        int m = grid.size();
        int n = grid[0].size();
        std::vector<std::vector<int>> res(m, std::vector<int>(n, 0));
        res[0][0] = grid[0][0];
        for (size_t i = 1; i < n; ++i) {
            res[0][i] = grid[0][i] + res[0][i-1];
        }
        for (size_t i = 1; i < m; ++i) {
            res[i][0] = grid[i][0] + res[i-1][0];
        }
        for (size_t row = 1; row < m; ++row) {
            for (size_t line = 1; line < n; ++line) {
                res[row][line] = std::min(res[row-1][line], res[row][line-1]) + grid[row][line];
            }
        }
        return res[m-1][n-1];
    }
};

时间复杂度：O(m * n) ，空间复杂度：O(m * n)

三、空间压缩

我们可以将空间复杂度压缩到 min{M,N}

假如本题目的矩阵如下：

我们生成一个长度为 3 的数组。

在第一次遍历时，我们给数组填上 {1, 4, 9}，代表的意思是 arr[0]: dp[0][0], arr[1]: dp[0][1], arr[2]: dp[0][2]。

好，我们开始第二次遍历，第二次遍历，我们希望求出 dp[1][0], dp[1][1], dp[1][2]。

而 dp[1][0] = dp[0][0]+grid[1][0]，我们把 dp[1][0] 赋给 arr[0]。
接着 dp[1][1] = min{dp[1][0],dp[0][1]}+grid[1][1]，而此时 dp[0][1] 就是上一次遍历中求得的 arr[1]，dp[1][0] 我们刚才已经求出来的，就是 arr[0] ，于是我们把 dp[1][1] 赋给 arr[1]
dp[1][2] = min{dp[1][1], dp[0][2]}+grid[1][2] ，和 dp[1][1]的求法一致，之后赋给 arr[2]

之后，我们再开始遍历。继续给 arr 赋值。我们发现，整个过程其实就是不断滚动更新 arr 数组，让 arr 依次变成 dp 矩阵每一行的值，最终变成 dp 矩阵最后一行的值。

还有一个细节需要注意，

如果给定的矩阵列数小于行数，那么 arr 数组的长度与矩阵列的长度一致
如果给定的矩阵行数小于列数，那么 arr 数组的长度与矩阵行的长度一致。然后 arr 更新为 dp 矩阵每一列的值，从左向右滚动过去。

class Solution2 {
public:
    int get_min_path_sum(const std::vector<std::vector<int>>& grid) {
        if (grid.empty()) {
            return 0;
        }
        int more = std::max(grid.size(), grid[0].size());
        int less = std::min(grid.size(), grid[0].size());
        bool row_more = more == grid.size();
        std::vector<int> arr(less, 0);
        arr[0] = grid[0][0];
        for (int i = 1; i < less; i++) {
            arr[i] = arr[i-1] + (row_more ? grid[0][i] : grid[i][0]);
        }
        for (int i = 1; i < more; i++) {
            arr[0] = arr[0] + (row_more ? grid[i][0] : grid[0][i]);
            for (int j = 1; j < less; j++) {
                arr[j] = std::min(arr[j-1], arr[j]) + (row_more ? grid[i][j] : grid[j][i]);
            }
        }
        return arr[less-1];
    }
};

时间复杂度：O(M*N)，空间复杂度：O(min{M, N})