Leetcode 連結

要理解這個問題，先從一個簡單的例子開始：一個 2x2 的迷宮。在這個迷宮中，你只能往右或往下移動。要到達右下角（[1, 1]），有兩條可能的路徑：

  1. 右 → 下
  2. 下 → 右

因此可以得出結論：對於 2x2 的迷宮，到達右下角共有 2 條不同路徑。

延伸到更大的網格

考慮一個更大的網格，例如 3x7 的迷宮。我們可以建構一個矩陣來表示到達每個格子的方法數。關鍵的觀察是：

到達格子 [i, j] 的方法數，等於到達其正上方格子（[i-1, j]）與正左方格子（[i, j-1]）的方法數之和。

逐步建構

  1. 首先初始化網格。第一列和第一行的每個格子都只有一種到達方式，因為只能往右或往下移動：
1, 1, 1, 1, 1, 1, 1
1,
1,

  1. 接著根據公式計算每個格子的值：

    • 格子 [1, 1]：
      m[1][1] = m[0][1] + m[1][0] = 1 + 1 = 2
      更新後的矩陣：
      1, 1, 1, 1, 1, 1, 1
      1, 2
      1,

  2. 繼續填寫矩陣：

    • 格子 [2, 1]：
      m[2][1] = m[1][1] + m[2][0] = 2 + 1 = 3
    • 格子 [1, 2]：
      m[1][2] = m[0][2] + m[1][1] = 1 + 2 = 3

    更新後的矩陣：

    1, 1, 1, 1, 1, 1, 1
    1, 2, 3
    1, 3

  3. 重複這個過程，最終可以填滿整個網格。對於 3x7 的網格，完成後的矩陣如下：

1, 1, 1, 1, 1, 1, 1
1, 2, 3, 4, 5, 6, 7
1, 3, 6, 10, 15, 21, 28

最終答案

矩陣右下角的值即代表不同路徑的總數。對於 3x7 的網格，共有 28 條不同路徑。

這個方法可以透過動態規劃推廣到任意大小的網格。藉由建構矩陣並依據相鄰格子之間的關係填值，就能有效率地計算任意 m x n 網格的不同路徑數。