64. 最小路徑和

記憶化搜索

根據題目，要想走到 $(x, y)$，可以從左邊或是上面來，也就是 $(x-1, y)$ 或 $(x, y-1)$。
那麼，對於格子 $(x, y)$ 來說，最好的路徑就是下面兩種選項擇一。

• 走到 $(x-1, y)$ 的最小成本加上grid[x][y]
• 走到 $(x, y-1)$ 的最小成本加上grid[x][y]

那麼走到這兩個點的最小成本是多少呢？把上面那段文字的 $(x, y)$ 改成 $(x-1, y)$ 和 $(x, y-1)$ 就行。

遞迴時，我們能事先存下已經算過的值，就能避免重複計算。
比如 $(x+1, y)$ 和 $(x, y+1)$，都會計算 $(x, y)$ 的最小成本，
在第二次計算時，將事先紀錄的數字填入即可。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        auto dfs = [&](this auto&& dfs, int x, int y) -> int {
            if(x < 0 || y < 0) return INT_MAX; // 遞迴終點
            if(x == 0 && y == 0) return grid[x][y]; 
            int& res = memo[x][y]; // 這裡是引用
            if(res != -1) { // 代表有算過
                return res;
            }
            res = min(dfs(x - 1, y), dfs(x, y - 1)) + grid[x][y];
            return res;
        };
        return dfs(m - 1, n - 1);
    }
};

複雜度分析

• 時間複雜度：$O(mn)$，每個位置都被算一次。
• 空間複雜度：$O(mn)$，需要存下每個位置。

動態規劃

第二個方法是動態規劃，其實就是把上面的遞迴改成迭代。
用dp[i][j]代表走到 $(i, j)$ 的最小成本。
在更新dp[i][j]時，一樣可以從兩個方向來

• dp[i-1][j] + grid[i][j]
• dp[i][j-1] + grid[i][j]

因此可以得到轉移方程

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, INT_MAX));
        dp[0][0] = 0; // 初始值為 0，而不是 grid[0][0]
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i - 1 >= 0) dp[i][j] = dp[i - 1][j];
                if(j - 1 >= 0) dp[i][j] = min(dp[i][j], dp[i][j - 1]);
                dp[i][j] += grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
};

複雜度分析

• 時間複雜度：$O(mn)$，每個位置都被算一次。
• 空間複雜度：$O(mn)$，需要存下每個位置。

狀態壓縮

最後，在更新dp矩陣時，被更新的數值會從左到右更新，然後來到下一行，
更新時，只會用到上一排的數值，和左邊的數值，因此只需要存這些「會被用到的資料」就好，
因此能壓縮矩陣，變成一維的樣子。

更新的寫法不同是因為一旦更新，前面一排的數據就丟失了。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                if(i - 1 >= 0 && j - 1 >= 0) {
                    dp[j] = min(dp[j], dp[j - 1]); // dp[j] = dp[i-1][j]
                }
                else if(j - 1 >= 0) {
                    dp[j] = dp[j - 1]; // 因為從左到右更新，dp[j - 1] = dp[i][j-1]
                }
                dp[j] += grid[i][j];
            }
        }
        return dp.back();
    }
};