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