647.?回文子串

動(dòng)規(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)過計(jì)算的

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.最長回文子序列

動(dòng)規(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ù)組