647.?回文子串
動規(guī)五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j]：表示區(qū)間范圍[i,j] （注意是左閉右閉）的子串是否是回文子串盟庞，如果是dp[i][j]為true舷蟀，否則為false
確定遞推公式
s[i]株汉！=s[j]?dp[i][j]=false
s[i]==s[j]
if(s[i]==s[j]){if(j-i<=1){// 情況一 和 情況二result++;dp[i][j]=true;}elseif(dp[i+1][j-1]){// 情況三result++;dp[i][j]=true;}}
dp數(shù)組初始化
dp[i][j]初始化為false
確定遍歷順序
從下到上冒版，從左到右遍歷液茎，保證dp[i + 1][j - 1]是經(jīng)過計算的
for(inti=s.size()-1;i>=0;i--){// 注意遍歷順序for(intj=i;j<s.size();j++){if(s[i]==s[j]){if(j-i<=1){// 情況一 和 情況二result++;dp[i][j]=true;}elseif(dp[i+1][j-1]){// 情況三result++;dp[i][j]=true;}}}}
舉例推導(dǎo)dp數(shù)組
516.最長回文子序列
動規(guī)五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j]：字符串s在[i, j]范圍內(nèi)最長的回文子序列的長度為dp[i][j]。
確定遞推公式
s[i]==s[j]??dp[i][j] = dp[i + 1][j - 1] + 2;
s[i]!=s[j]?dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
if(s[i]==s[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=max(dp[i+1][j],dp[i][j-1]);}
dp數(shù)組初始化
當(dāng)i與j相同，那么dp[i][j]等于1,其余情況初始化0
確定遍歷順序
dp[i][j] 依賴于 dp[i + 1][j - 1] 捆等，dp[i + 1][j] 和 dp[i][j - 1]
從下到上滞造。從左往右遍歷
for(inti=s.size()-1;i>=0;i--){for(intj=i+1;j<s.size();j++){if(s[i]==s[j]){dp[i][j]=dp[i+1][j-1]+2;}else{dp[i][j]=max(dp[i+1][j],dp[i][j-1]);}}}
舉例推導(dǎo)dp數(shù)組
