主題
題目連結：
題目意譯：
在一個大小為 m × n 的金礦網格 grid 上，每一格都有一個整數代表著該格的黃金含量。如果其值為 0，則代表該格是空的。
回傳根據以下規則你可以收集到的最大黃金量：
每次踩在有黃金的格子上你必定會收集該格所有的黃金；
從當前所在格子，你可以往上、下、左或右走一格；
你不得走到先前已經走到過的格子；
不得走到黃金量為 0 的格子；
你可以從 grid 中挑選任意一格有黃金的格子來開始收集黃金，也可以在任意時間點停止收集。
限制：
m == grid.length
n == grid[i].length
1 ≦ m, n ≦ 15
0 ≦ grid[i][j] ≦ 100
最多只有 25 個包含黃金的格子。
範例測資：
範例 1：
輸入： grid = [[0,6,0],[5,8,7],[0,9,0]]
輸出： 24
解釋：
[[0,6,0],
[5,8,7],
[0,9,0]]
可以得到的最大黃金量之路徑為 9 → 8 → 7。
範例 2：
輸入： grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
輸出： 28
解釋：
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
可以得到的最大黃金量之路徑為 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。
解題思維：
就直接掃過整個網格，然後找到每一格包含黃金的格子並窮舉從該格作為開頭的所有可能路徑即可。
因此最糟時間複雜度為 O(m × n + g × 3 ^ g)，其中 g 為含有黃金的格子。3 ^ g 是因為對於每一格（除了開頭格子）來說最多只會有 3 個可能的方向可以走，因為不得回頭。
是的，時間複雜度就是這麼大。但是不用擔心，在實務上會遠小於 g × 3 ^ g 條路徑。
例如說把 25 個有黃金的格子直接聚集在一起形成一個 5 × 5 的區域最多也只會有 3060417 條不同的路徑。如果是極大化路徑數（意即走到不能再走的那些路徑）只會有 798312 條。而這很明顯地遠小過 25 × 3 ^ 25。
注：如果有人知道比上面的時間複雜度更緊的上界又或是有其他作法有更確切且更小的時間複雜度，請讓我知道。還有如果有人找到比 5 × 5 的矩形區域還要更多的路徑數之圖形，也請告知我。謝謝。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
