Python-LeetCode 581 第14招 Dynamic Programming I： 基本原理與一維DP
談到
「設計DP以尋找遞迴式開始，以避免遞迴來完成，除非，除非你準備小抄。」

設計DP的演算法通常包含下面幾個步驟：

1. 定義子問題。
2. 找出問題與子問題之間的(遞迴)關係。
3. 找出子問題的計算順序來避免以遞迴的方式進行計算。

以下開始今天的練習題。

64. Minimum Path Sum (medium)

RECURSIVE

題目描述：
給定一個 m x n 的非負整數矩陣，找到一條從左上角到右下角的路徑，使得路徑上的數字總和最小。每次只能向下或向右移動一步。

解題思路：
雖然題目要求從 (0, 0) 走到 (n-1, m-1)，但我懶得在函式多加兩個參數，所以我決定反著走，從 (n-1, m-1) 走回 (0, 0)。

• 子問題定義： dfs(n, m) 表示從 (0, 0) 走到 (n, m) 的最小路徑和
• 遞迴關係: dfs(n, m) = min(dfs(n-1, m), dfs(n, m-1)) + grid[n][m]
• 基礎:
  • 當 n == 0 && m == 0，返回 grid[0][0]
  • 當 n < 0 || m < 0，返回 INT_MAX，表示不可達

class Solution {
public:
    int dfs(int n, int m, vector<vector<int>>& grid) {
        if (n == 0 && m == 0) 
            return grid[0][0];
        if (n < 0 || m < 0) 
            return INT_MAX;
        return min(dfs(n-1, m, grid), dfs(n, m-1, grid)) + grid[n][m];
    }

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

時間複雜度: 含大量重疊子問題，O(2^{m+n})

Top-Down DP

使用額外陣列(dp)，存已計算過的值，避免重複計算。

class Solution {
public:
    int dfs(int n, int m, vector<vector<int>>& grid, vector<vector<int>>& dp) {
        if (n == 0 && m == 0) 
            return grid[0][0];
        if (n < 0 || m < 0) 
            return INT_MAX;
        if (dp[n][m])
            return dp[n][m];
        dp[n][m] = min(dfs(n-1, m, grid, dp), dfs(n, m-1, grid, dp)) + grid[n][m];
        return dp[n][m];

    }

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

時間複雜度: 因每個子問題只計算一次，共一個 O(m * n)

BOTTOM UP dp

• 子問題: dp[i][j] 表示 從 grid(0, 0) 到 grid(i, j) 的最小路徑和。
• 遞迴: dp[i][j] = min(dp[n-1][m], dp[n][m-1]) + grid[n][m]
  為
  我為了避免處理邊界條件，將 dp 的最外層（即 dp[0][*] 和 dp[*][0]）初始化為無限大（INF），這樣在計算時如果索引超出範圍，不會影響最小值的判斷。

範例

   grid          dp
---------------------------
 0 0 0 0       0  INF INF INF
 0 1 3 1     INF   1   4   1
 0 1 5 1  -> INF   2   7   6 
 0 4 2 1     INF   6   8   7

    grid                     dp
------------------------------------------
 100 100 100 100        0  0  INF INF INF
                   -> INF 100 200 300 400

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<int>> dp(n+1, vector<int>(m+1, INT_MAX / 2));

        dp[0][1] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i-1][j-1];
            }
        }
        return dp[n][m];
    }
};

時間複雜度: O(m * n)

此題還可以改成 1維 DP，這將在明日討論。

補充昨日的 62. Unique Paths

題目: 計算(0, 0) 到 (m, n) 有多少獨特路徑。

遞迴式: dp[i][j] = dp[i-1][j] + dp[i][j-1];
這表示到達位置 (i, j) 的路徑數等於從上方來的路徑數加上從左方來的路徑數

    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1]; 
    }

時間複雜度: O(M * N)，因為要迭代整個網格。