主題
題目連結：
題目意譯：
現在有一個 m × n 網格以及一顆球。那顆球原本在位置 [startRow, startColumn] 上。你被允許將球移動到其在 grid 中的四個相鄰格子（可能會跨過 grid 的邊界而跑到 grid 外面）。你可以只能移動那顆球 maxMove 次。
給定五整數 m 、 n 、 maxMove 、 startRow 、 startColumn ，回傳將球移出 grid 的邊界之路徑數量。由於答案可能很大，因此將其模 10 ^ 9 + 7 後回傳。
限制：
1 ≦ m 、 n ≦ 50
0 ≦ maxMove ≦ 50
0 ≦ startRow < m
0 ≦ startColumn < n
範例測資：
範例 1：
輸入： m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
輸出： 6
範例 2：
輸入： m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
輸出： 12
解題思維：
我們可以利用動態規劃（Dynamic Programming）的精神得到所求。
我們知道一開始，第一步只會有邊界可以跑出去邊界外。例如一個 4 × 3 的網格為
2 1 2
1 0 1
1 0 1
2 1 2
其中每個位置的數字代表其跑出邊界外的方法數。
因此我們可以定義一個三維陣列 D[i][j][k] ，代表著第 i 列第 j 行這個位置在可以移動 k 步的情況下，會移出邊界外的路徑之數量。
而我們已經知道第一步（k = 1）的情況（如上面的 4 × 3 網格）。接著我們就可以按照遞迴式
D[i][j][k] = D[i-1][j][k] + D[i][j-1][k] + D[i+1][j][k] + D[i][j+1][k]
（此即四個相鄰位置，不過記得判斷邊界，忽略掉超出邊界的格子）
而推得 k = 2 、 3 、 4 、…… 時的情況。
例如上面的 4 × 3 網格，其 k = 2 時會得到
2 4 2
3 3 3
3 3 3
2 4 2
而 k = 3 時會得到
7 7 7
8 13 8
8 13 8
7 7 7
……
因此所求即為 D[R][C][1] + D[R][C][2] + …… D[R][C][maxMove] ，其中 R = startRow 、 C = startColumn 。不過要記住，每次運算之後記得模（取餘數）10 ^ 9 + 7 以免溢位。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
