題目描述：

給你一個字符串?s，找到?s?中最長的回文子串。

解法：動態(tài)規(guī)劃

維基百科：動態(tài)規(guī)劃（英語：Dynamic programming，簡稱 DP），是一種在數(shù)學(xué)、管理科學(xué)、計算機科學(xué)、經(jīng)濟學(xué)和生物信息學(xué)中使用的，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。

以該題為例：首先，從示例中可看出該題可能是不唯一解，我們需要從所給的字符串s中，找到滿足符合條件的子字符串。簡單的說，我們需要遍歷字符串s的任意長度的子字符串，再通過條件判斷，返回最長的子字符串。

判斷過程：

我們通過字符串s對長度建立一個正二維表，使用兩個指針，一個指針i從索引1的位置開始鎖定，另一個指針j從索引0的位置到一直遍歷到第一個指針的位置。令 dp[i][j]?表示 S[i]?至 S[j]?所表示的子串是否是回文子串，是則為 True，不是則為False。這樣根據(jù) S[i]?是否等于 S[j] ，可以把轉(zhuǎn)移情況分為兩類：

?1.若 S[i] == S[j]，那么只要 S[i+1]?至 S[j-1]?是回文子串，S[i]?至 S[j]?就是回文子串；如果S[i+1]?至 S[j-1]?不是回文子串，則 S[i]?至 S[j]?也不是回文子串。

?2.若 S[i] != S[j]，那么 S[i]?至 S[j]?一定不是回文子串。

依次進(jìn)行對比：

源代碼：

去試試吧！