64. 最小路径和

题目链接

这道题目与62.不同路径很像，来到[i, j]位置，只能向下，或者向右走，只不过改题是要求总和最小。

• process(i, j)：当前在[i, j]位置，返回最小路径和
• 所以当在[i, j]，如果还能往下走，一种答案就是process(i + 1, j) + grid[i][j]
• 如果还能往右走，另一种答案就是process(i, j + 1) + grid[i][j]
• 两种答案取最小值即可，可以发现，又是暴力递归，两个可变参数，所以直接加缓存即可。

代码

class Solution {
public:
    // 现在在[i, j]，返回到达右下角时，最小的路径和   m是行数  n是列数
    int process(const vector<vector<int>>& grid, int i, int j, const int m, const int n, vector<vector<int>> &dp) {
        if (i == m - 1 && j == n - 1) {    // 到达右下角了   直接返回
            return grid[i][j];
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int ans = INT32_MAX;
        if (i < m - 1) {    // 还能往下走
            ans = min(ans, process(grid, i + 1, j, m, n, dp) + grid[i][j]);
        }
        if (j < n - 1) {    // 还能往右走
            ans = min(ans, process(grid, i, j + 1, m, n, dp) + grid[i][j]);
        }
        dp[i][j] = ans;
        return ans;
    }

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>>  dp(m, vector<int>(n, -1));
        return process(grid, 0, 0, m, n, dp);
    }
};