二維動態(tài)規(guī)劃思路：

?????????首先，剛做完這道題：力扣---最長有效括號---動態(tài)規(guī)劃，棧-CSDN博客，所以會有一種沖動，設(shè)立g[i]，表示以第i位為結(jié)尾的最長回文子串長度，然后再遍歷一遍取最大長度即可。但是，后來發(fā)現(xiàn)如果g[i]如此表示，很難得到遞推公式。所以轉(zhuǎn)到二維，設(shè)立g[i][j]（bool），將其表示以第i位開頭第j位結(jié)尾的子串是否是回文子串，并用l和r記錄到目前為止最長回文子串的左索引和右索引。所以，遞推公式為g[i][j]={如果s[i]==s[j]且g[i+1][j-1]是回文子串，則為1}。此時有需要獨立判斷兩種情況：第一種情況是子串長度為1，g[i][i]=1，第二種情況是子串長度為2(j-i==1)，如果s[i]==s[j]，則g[i][j]=2。

? ? ? ? 還要說明一點，為什么在二重循環(huán)時，i 的順序是從len-1到0，j 的順序是從i到len。因為由g[i+1][j-1]推及g[i][j]，所以我們需要先從左下角向右上角開始推，行數(shù)(i)從大到小，列數(shù)(j)從小到大。

代碼：

C++：

class Solution {
public:string longestPalindrome(string s) {int len=s.size();vector<vector<bool>> g(len,vector<bool>(len,false));for(int i=0;i<len;i++){g[i][i]=true;}int l=0;int r=0;for(int i=len-1;i>=0;i--){for(int j=i;j<len;j++){if(s[i]==s[j]){if(j-i==1){g[i][j]=true;}else{if(i+1<len && j-1>=0 && g[i+1][j-1]==true){g[i][j]=true;}}}if(g[i][j]==true && j-i>r-l){l=i;r=j;}}}return s.substr(l,r-l+1);}
};

Python：

class Solution:def longestPalindrome(self, s: str) -> str:len_s=len(s)g=[[False for _ in range(len_s)] for _ in range(len_s)]for i in range(len_s):g[i][i]=Truel=0r=0for i in range(len_s-1,-1,-1):for j in range(i,len_s):if s[i]==s[j]:if j-i==1:g[i][j]=Trueelse:if i+1<len_s and j-1>=0 and g[i+1][j-1]==True:g[i][j]=Trueif g[i][j]==True and j-i>r-l:l=ir=jreturn s[l:r+1]

注意這句話的寫法：

g=[[False for _ in range(len_s)] for _ in range(len_s)]