LeetCode 64 Minimum Path Sum

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2020-06-25 11:26:49
    编辑于：2022-02-19 13:11:43
    浏览量：1459

题目分析

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

该题有以下几种状态定义：

设 store[i][j] 是从点 (i, j) 到右下角的最短路径长。
设 store[i][j] 是从左上角到点 (i, j) 的最短路径长。

递归解法

递归解法没什么好解释的，要注意的是别忘了考虑边界情况。

class Solution {
public:
    vector<vector<int>> store;
    int m, n;
    int minPathSum(vector<vector<int>>& grid) {
        m = grid.size();
        n = grid[0].size();
        store = vector(m, vector<int>(n, -1));
        store[m-1][n-1] = grid[m-1][n-1];
        return dp(0, 0, grid);
    }
    
    // Return the minimum sum from (row, col) to bottom right
    int dp(int row, int col, vector<vector<int>>& grid) {
        if (row >= m || col >= n) return INT_MAX;
        if (store[row][col] != -1) return store[row][col];
        return store[row][col] = grid[row][col] + min(dp(row, col+1, grid), dp(row+1, col, grid));
    }
};

时间复杂度 O(nm)，因为 grid 里的每个值都至多被计算一次。

空间复杂度 O(nm)，因为我们要维护一个 store 用以存储计算过的结果。

注意到：store[m-1][n-1] = grid[m-1][n-1]; 以及 store[row][col] = grid[row][col] + min(dp(row, col+1, grid), dp(row+1, col, grid)); ，

我们发现用到 grid[row][col] 必然用到 store[row][col]，自然联想到可不可以直接使用 grid 储存计算过的值，这样使空间复杂度降到 O(1)？

但是如何判断该位置是否已经计算过是个问题。

一种显然的方法是用一个二维数组来记录是否访问过，虽然占用的存储空间变少了，但是空间复杂度没有变化，因此这里不予考虑。

回想一下，我们之所以需要一个数组来记录是因为访问 store[row, col] 时我们不知道其是不是已经被计算过了，如果按照某个特定的顺序去访问，我们就可以保证其是计算过的。此时使用迭代形式的解更方便些。

迭代解法

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int row = m - 1; row >= 0; --row) {
            for (int col = n - 1; col >= 0; --col) {
                int right = col == n - 1 ? INT_MAX : grid[row][col + 1];
                int below = row == m - 1 ? INT_MAX : grid[row + 1][col];
                grid[row][col] += min(right, below) == INT_MAX ? 0 : min(right, below);
            }
        }
        return grid[0][0];
    }
};

但是这内存占用就少了这么点？

我们看看有什么可以优化的地方。

注意到为了处理边缘的情况，我们在每次循环都进行了四次非必要的判断。

改进一下：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int row = m - 2; row >= 0; --row) {
            grid[row][n-1] += grid[row+1][n-1];
        }
        for (int col = n - 2; col >= 0; --col) {
            grid[m-1][col] += grid[m-1][col+1];
        }
        for (int row = m - 2; row >= 0; --row) {
            for (int col = n - 2; col >= 0; --col) {
                grid[row][col] += min(grid[row][col+1], grid[row+1][col]);
            }
        }
        return grid[0][0];
    }
};

然而 Runtime 以及 Memory 并没有变化，我佛了。

2022年2月19日的递归解法

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

Links: LeetCode-64-Minimum-Path-Sum