主題
題目連結：
題目意譯：
一個括號字串為一個非空字串，其只由 '(' 和 ')' 所組成。如果下列之一的條件滿足的話，則該字串合法：
其為 ()；
其可以被寫為 AB （A 串接著 B）之形式，其中 A 和 B 皆為合法的括號字串；
或是其可以被寫為 (A) 之形式，其中 A 為一個合法的括號字串。
你給定一個 m × n 個括號矩陣 grid。grid 中一個合法的括號字串 path 為一個滿足以下全部條件的一條路徑：
路經開始於左上角格子 (0, 0)、
路徑結束於右下角格子 (m - 1, n - 1)、
路徑中只會往下或是往右走、
路徑所形成的括號字串是合法的。
如果 grid 中存在一個合法的括號字串 path，則回傳真（True）；反之，則回傳假（False）。
限制：
m == grid.length
n == grid[i].length
1 ≦ m, n ≦ 100
grid[i][j] 只會是 '(' 或是 ')'。
範例測資：
範例 1：
輸入： grid = [["(","(","("],[")","(",")"],["(","(",")"],["(","(",")"]]
輸出： true
解釋： 上圖顯示了兩條形成了合法括號字串的可能路徑。
圖示第一條路徑形成了合法括號字串 "()(())"。
圖示第二條路徑形成了合法括號字串 "((()))"。
注意到可能會有其他的合法括號字串存在。
範例 2：
輸入： grid = [[")",")"],["(","("]]
輸出： false
解釋： 兩種可能的路徑形成了字串 "))(" 和 ")(("。由於兩者都不是合法的括號字串，我們回傳假。
解題思維：
今天我們要需要前幾天提及到的用來判斷一個括號字串是否合法會使用的變數。稱其為 balance（注意這是一個在過程中會變動的數值）。
可以看到 balace < 0 時，代表該括號字串肯定不合法（因為有太多右括號先於左括號出現）；balance = 0 時，代表目前左右括號剛好平衡；而 balance > 0 時，則代表還尚有機會是一個合法的括號字串（只是需要等待更多的右括號與前面的左括號來配對而已）。
接著我們使用動態規劃（Dynamic Programming，DP）的精神來解出本題：
定義一個三維陣列 D，其中 D[i][j][k] 代表 grid 中左上角 (0, 0) 到右下角 (i, j) 這個子矩陣之中，有多少條路徑從左上角到右下角使得形成的括號字串之最終 balance 為 k。因此可以看到所求會是 D[m - 1][n - 1][0]。
其遞迴式為：
對於 i < 0 或 j < 0 或 k < 0，D[i][j][k] = 0；
對於 grid[i][j] == '('，D[i][j][k + 1] = D[i - 1][j][k] || D[i][j - 1][k]；
對於 grid[i][j] == ')'，D[i][j][k - 1] = D[i - 1][j][k] || D[i][j - 1][k]。
（其中「||」代表著邏輯「或」之操作）
因為對於 grid[i][j] 這個格子，根據題目我們只能從「上方」（grid[i - 1][j]）或「左方」（grid[i][j - 1]）過來。而以 grid[i][j] 作為結尾的括號字串之 balance 值可能有很多種，所以我們每一種都窮舉求求看。
因此我們可以從 grid[0][0] 開始掃過每一列，對於每一列掃過每一行，然後對於每個格子 grid[i][j] 窮舉所有可能的 balance 值（其範圍為 0 ～ i + j，因為此時括號字串長度為 i + j，而 balance < 0 之部分不需考慮）。接著按照上列的遞迴式依序求解即可。
最後，DP[m - 1][n - 1][0] 即為所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
