LeetCode短影片 | 最長有效括弧使用棧很容易解決，但偏用動態規劃

題目如下：

看了這個題目的標籤，動態規劃是其的標籤之一。這題目我第一反應可以使用棧來解決，但我們偏用動態規劃看看解決的是什麼樣子的。

我們定義一個dp[i]數組，其中i表示字元串的下標，值是目前有效的子字元串。

我們將dp數組全部初始化為0。

現在，很明顯有效的子字元串一定以『)』結尾。

我們可以進一步得出結論：以『(』的子字元串對應位置上的值必定為0。

所以說我們只需要更新『)』在dp數組中對應位置的值。

為了求出dp數組，我們每兩個字元檢查一次，如果滿足如下條件

s[i]=『)』且s[i−1]=『(』，形如『『…()…"，可以推出：dp[i]=dp[i−2]+2

可以進行這樣的轉移，是因為結束部分的"()"是一個有效子字元串，並且將之前有效子字元串的長度增加了2。

s[i]=『)』且s[i−1]=『)』，也就是字元串形如『『…))…"，我們可以推出：

如果s[i−dp[i−1]−1]=『(』，則dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2

這背後的原因是如果倒數第二個『)』是一個有效子字元串的一部分（記為s），對於最後一個『)』，如果它是一個更長子字元串的一部分，那麼它一定有一個對應的『(』，它的位置在倒數第二個『)』所在的有效子字元串(s)的前面。

因此，如果子字元串s的前面恰好是『(』，那麼我們就用2加上s的長度（dp[i−1]）去更新dp[i]。

除此以外，我們也會把有效子字元串『『(,s,)"之前的有效子字元串的長度也加上，dp[i−dp[i−1]−2]。

Java程式碼：

——END——