代码随想录算法训练营第五十九天|647. 回文子串、516.最长

647. 回文子串

动规五部曲

确定dp数组（dp table）以及下标的含义

dp[i][j]：表示区间范围[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数组初始化

dp[i][j]初始化为false

确定遍历顺序

从下到上，从左到右遍历，保证dp[i + 1][j - 1]是经过计算的

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;}}}}

举例推导dp数组

516.最长回文子序列

动规五部曲

确定dp数组（dp table）以及下标的含义

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为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数组初始化

当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]);}}}

举例推导dp数组