LeetCode短視頻 | 最長迴文子串，使用動態規劃的通俗分析

前面一章中，介紹了什麼是動態規劃，傳送地址：這裡。

為確保理解什麼是迴文。

迴文是一個正讀和反讀都相同的字符串，例如，「aba」是迴文，而「abc」不是。

當子串只包含1個字符，它一定是迴文子串；

當子串包含2個以上字符的時候：如果s[l, r]是一個迴文串，s[l + 1, r – 1] 也一定是迴文串。

例如「abccba」，那麼這個迴文串兩邊各往裏面收縮一個字符（如果可以的話）的子串s[l + 1, r – 1]也一定是迴文串，即：如果dp[l][r] == true成立，一定有dp[l + 1][r – 1] = true成立。

使用動態規劃解決此問題的步驟：

1. 定義一個二維數組bool dp[len-1][len-1]來記錄遍歷字符串所得的狀態，dp[l][r]為true表示從l到r的子串為迴文串，false表示不是迴文串

2. 初始化二維數組，單個字符為迴文串，所以定義dp[i][i] = true

3. 找到狀態轉移方程，dp[l][r] = (s[r]==s[l] &&(r-l==1 || dp[l+1][r-1])) ? true : false

話不多說，直接上短視頻吧：

貼代碼：

——END——