從LeetCode學演算法 - 90 Dynamic Programming (11) / DFS (9)

0576. Out of Boundary Paths (Medium)

Question

There is an m by ** n** grid with a ball. Given the start coordinate ** (i,j)** of the ball, you can move the ball to an ** adjacent** cell or cross the grid boundary in four directions (up, down, left, right). However, you can ** at most** move ** N** times. Find out the number of paths to move the ball out of the grid boundary. The answer may be very large, return it after mod 10⁹ + 7.

Example 1

1
2
3
Input: m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:

Example 2

1
2
3
Input: m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:

Note:

Once you move the ball out of the boundary, you cannot move it back.
The length and height of the grid are in the range [1,50].
N is in range [0,50].

分析/解題

題目描述有一組 m * n 的方格，格子上有一個球，其起始座標為 (i, j)，
你可以將球移到四個方向內沒超過邊界的格子，但最多只能移動N次。
試算出所有會將球移超過邊界的路徑數目。
限制：

一旦移出邊界就不能再回來(也就是直接遊戲結束了)
格子的寬高均在1~50的範圍
總次數N在0~50的範圍
另由於答案可能非常大，回傳結果要先除以10的9次方+7。

我們先思考關於路徑超過邊界的狀態。
要被算做是其中一種的話，首先最後一步一定要是從格子內移到格子外 ，
也就是要在邊界才可以，只差一格index就小於0 或**>m-1** (或n-1 )。
畢竟不在懸崖邊怎麼可能會有掉下懸崖的可能對吧XD！
並且，因為掉下去就回不來了 ，所以路徑就會到此為止。
(當然不管剩下的步數，你總不會飛簷走壁吧@@)

接著，當 N=0 時，
由於根本沒辦法動，自然不會有符合的路徑 ，答案為0。
N = 1 時，則要** 看你四邊有幾個懸崖對吧！
那N = 2呢？
是不是就要先看這一步有幾種可能會掉下去，加總起來以後** ，
接下來先走到不會掉下去的地方，再看那幾個有幾種情況會掉下去。
由於每走一步路，可用的步數就會少1，
我們終究會要嘛掉下去 ，要嘛走到沒有步數可用；
將所有加總起來，就得到答案了。

這個方式聽起來很DFS對吧？
所以按照上面的直覺，也許你會寫成像這樣子的內容：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# Will TLE
class Solution:
    def findPaths(self, m: int, n: int, N: int, i: int, j: int) -> int:
        def dfs(i, j, N):
            res = 0
            if N != 0:
                res += 1 if i - 1 < 0 else dfs(i-1, j, N-1)
                res += 1 if i + 1 == m else dfs(i+1, j, N-1)
                res += 1 if j - 1 < 0 else dfs(i, j-1, N-1)
                res += 1 if j + 1 == n else dfs(i, j+1, N-1)
            return res
        res = dfs(i, j, N)
        return res % (10 ** 9 + 7)

當方向會掉下去的時候，就代表方法數加1；
否則的話，就要往那個方向走1步去算可能的方法。
你會發現測試一般的結果可以算出正確答案，
但大一點的數字會算到超時，為什麼呢？

其實理由跟以前我們算Fibonacci數列時一樣，
這樣子的寫法會導致每一個數都是從單一個1累加起來的，
中間我們可能走到同樣的格子，剩下相同的步數，
卻沒有利用到這點，從而導致效率超級差。

那怎麼辦呢？
當我們同時考慮動態規劃的觀念時，
就容易想到，我們可以將先前算過的東西當成已知的內容儲存起來，
當再碰到時，就可以直接取用計算。
在本例當中，影響到結果的值有i, j, N，
所以我們可以選擇使用一個三維的陣列/串列 ，(也可以用兩個二維陣列)
或者Python內也可以用字典來做對應儲存。
扣除掉這點以外，跟前面的寫法並無不同，讀者可以自行參照看看。

那麼，有沒有別種思考的方式呢？
有的，像是lee215就提供了另一種思路：
我們最開始N=0時，整個盤面不論i, j為什麼，
(i, j, 0)的結果都會是0，而(i, j, N)的結果，
則取決於**(i, j)上下左右4格在N-1步的時候** 的結果。
如果該格超出邊界，則至少從(i, j)有1步可以走出邊界，
反之，(i, j)可以花1步走過去。
因此，我們可以一次一次更新整個盤面，
從而算得第N步的結果。(參見Python lee215解 )

或者，我們也可以從i, j為起點，
記錄從i, j到某一格的總路徑數量 ，
每當有機會超出邊界時，則將該部分加總到結果中，
兩個方法殊途同歸，最後都可以得到解答。(參見Java shawngao解)

依照上面的這些想法，我們可以寫成解答：

Java

在Java的部分，除了上面提過的遞進計算整個盤面，
(使用兩個二維陣列交替)
也可以用三維陣列去記錄結果，
留意為了要偵測是否有記錄結果，
我們要用Arrays.fill()，將初始化的陣列都填入-1，
這樣我們才知道這個值它是0還是未填入的狀態。

Python

Python的部分，除了lee215的解法外，
我們也可以如上面提到的採用一個字典來進行儲存先前已計算過的內容。
此外，由於在這個問題中，
鏡像對稱位置的點在相同的N值下應該會有相同的答案，
所以還可以透過對稱的方式來進一步化簡所需的計算數量。
(可以看註解底下最後一個解，65~69行的部分)

面試實際可能會遇到的問題

「時間/空間複雜度？」
(時間複雜度方面，原則上最壞的狀況就是每個步驟算完整個盤面，
所以會是O(m*n*N) 。
空間複雜度的話，使用三維陣列或字典 的話是O(m*n*N) ，
而使用兩個二維陣列交替記錄 的話則是O(m*n) )

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(最後一波早鳥優惠了，不確定調回原價是什麼時候)： ** https://hiskio.com/courses/319?promo_code=VE9Q5VE**