Problem: 62. 不同路徑

整體思路

這段代碼同樣旨在解決 “不同路徑” 問題，但它采用的是一種 自底向上（Bottom-Up）的動態規劃 方法，也稱為 迭代法 或 制表法 (Tabulation)。這種方法通過構建一個DP表（dp 二維數組），從起點開始，逐步計算出到達每個格子的路徑數，最終得到終點的答案。

該實現通過巧妙地增加DP數組的維度（使用 m+1 和 n+1），將邊界條件的處理融入到統一的狀態轉移方程中，使得代碼非常簡潔。

1. 狀態定義與索引映射：

   • 算法定義了一個二維DP數組 dp，大小為 (m+1) x (n+1)。
   • dp[i][j] 的含義是：從起點 (1, 1)（對應 nums[0][0]）到達網格中的點 (i, j) 的不同路徑數。
   • 這是一個索引偏移的技巧。dp 數組的索引 (i, j) 對應了 m x n 網格中的索引 (i-1, j-1)。這樣做的好處是，dp 數組的第0行和第0列可以作為天然的邊界，避免了在循環中進行 i>0 或 j>0 的判斷。

2. 基礎情況 (Base Case)：

   • dp[1][1] = 1：這是整個DP計算的起點。它表示從起點到達起點 (1,1)（即 grid[0][0]）只有1條路徑（原地不動）。
   • dp 數組的其他元素默認初始化為 0。dp 的第0行和第0列全為0，這恰好滿足我們的邊界條件：無法從網格外部進入，路徑數為0。

3. 狀態轉移 (State Transition)：

   • 算法使用兩層嵌套循環來填充DP表。循環變量 i 和 j 對應的是 m x n 網格的索引。
   • 在循環的每一步，計算 dp[i+1][j+1] 的值。
   • 狀態轉移方程是 dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1]。
   • 我們來解析這個方程：
     • 要到達 dp 中的點 (i+1, j+1)（對應 grid[i][j]），只能從其左邊的點 (i+1, j)（對應 grid[i][j-1]）或上邊的點 (i, j+1)（對應 grid[i-1][j]）過來。
     • 因此，到達 (i+1, j+1) 的總路徑數，就是到達這兩個點的路徑數之和。
     • 當 i=0 或 j=0 時，例如計算 dp[1][j+1]，方程變為 dp[1][j+1] = dp[1][j] + dp[0][j+1]。因為 dp[0][j+1] 總是0，所以 dp[1][j+1] = dp[1][j]，這正確地表示了第一行所有格子的路徑數都為1。對第一列同理。

4. 返回結果：

   • 當所有循環結束后，dp 數組已經完全填充。我們需要的最終答案，即到達終點 grid[m-1][n-1] 的路徑數，就存儲在 dp[m][n] 中。

完整代碼

class Solution {/*** 計算從 m x n 網格的左上角到右下角的不同路徑數。* @param m 網格的行數* @param n 網格的列數* @return 不同的路徑總數*/public int uniquePaths(int m, int n) {// dp: 動態規劃數組。dp[i][j] 表示從起點到網格 (i-1, j-1) 的路徑數。// 使用 m+1, n+1 的大小是為了用第0行和第0列作為邊界，簡化代碼。int[][] dp = new int[m + 1][n + 1];// 基礎情況：到達起點 (0,0) 的路徑數是 1。// 在我們的 dp 表中，這對應 dp[1][1]。dp[1][1] = 1;// i 和 j 是原始網格的索引 (0-based)for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 跳過我們已經設置的起點if (i == 0 && j == 0)continue;// 狀態轉移方程：// 到達網格 (i, j) 的路徑數，等于到達其上方格子 (i-1, j)// 和左方格子 (i, j-1) 的路徑數之和。// 在 dp 表中，這對應于：// dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j]dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1];}}// 最終答案是到達網格 (m-1, n-1) 的路徑數，對應 dp[m][n]。return dp[m][n];}
}

時空復雜度

時間復雜度：O(m * n)

1. 循環結構：算法使用了兩層嵌套的 for 循環。
   • 外層循環從 i = 0 運行到 m-1，執行 m 次。
   • 內層循環從 j = 0 運行到 n-1，執行 n 次。
2. 計算依據：
   • 總的操作次數（主要是加法和賦值）是內外層循環次數的乘積，即 m * n。

綜合分析：
算法的時間復雜度為 O(m * n)。

空間復雜度：O(m * n)

1. 主要存儲開銷：算法創建了一個名為 dp 的二維整型數組來存儲動態規劃的所有中間狀態。
2. 空間大小：該數組的大小是 (m + 1) * (n + 1)。

綜合分析：
算法所需的額外空間主要由 dp 數組決定，其空間復雜度為 O(m * n)。