题目1：647 回文子串
题目链接：回文子串
对题目的理解
返回字符串s中回文子串的个数，字符串s至少包含一个字符，且仅由小写字母组成。
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i][j]：[i,j]子串是否为回文子串，代表以s[i]为开头，s[j]为结尾的子串（左闭右闭）
2）递推公式
整体可以分为两种情况，s[i]==s[j] s[i]!=s[j]
当s[i]等于s[j]时，有3种情况需要考虑：
j==i 两元素重合，代表数组中只有1个元素，那么必是回文子串
j-i==1 两元素相邻，代表数组中有两个元素，且前提是两个元素相等，那么这也必是回文子串
j-i>1 两元素不相邻，但是首尾的两元素相等，仅仅在dp[i+1][j-1]是回文串的基础上，dp[i][j]才是回文串
s[i]!=s[j]时，当前子串一定不是回文串，dp[i][j]=false
3）dp数组初始化
根据dp数组的定义，将其进行初始化，初始化为false,
4）遍历顺序
根据递推公式，从下往上遍历，从左往右遍历
5）打印dp数组
代码
class Solution {
public:
int countSubstrings(string s) {
//定义并初始化dp数组
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
int result = 0;
for(int i=s.size()-1;i>=0;i--){
for(int j=i;j<=s.size()-1;j++){
if(s[i]==s[j]){
if(j-i<=1){
dp[i][j]=true;
result++;
}
else if(dp[i+1][j-1]==true){
dp[i][j]=true;
result++;
}
}
}
}
return result;
}
};- 时间复杂度：O(n^2)
- 空间复杂度：O(n^2)
代码流程
法2：双指针法
首先确定回文串，就是找中心然后向两边扩散看是不是对称的就可以了。
在遍历中心点的时候，要注意中心点有两种情况：
1）一个元素可以作为中心点；
2）两个元素也可以作为中心点。
三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到，以此类推，因此，只分析一个元素作为中心点和两个元素作为中心点就可以了
代码
class Solution {
public:
int extend(string& s,int i,int j,int n){
int res;
while(i>=0 && j<n && s[i]==s[j]){
i--;
j++;
res++;
}
return res;
}
int countSubstrings(string s) {
int result = 0;
for(int i=0;i<s.size();i++){
result += extend(s,i,i,s.size());
result += extend(s,i,i+1,s.size());
}
return result;
}
};以上代码对于案例会计算错误，如图，原因就是未对res进行初始化
注意一定要对res进行初始化，不然会报以上错误，将代码修改为如下，就能够运行了
class Solution {
public:
int extend(string& s,int i,int j,int n){
int res=0;
while(i>=0 && j<n && s[i]==s[j]){
i--;
j++;
res++;
}
return res;
}
int countSubstrings(string s) {
int result = 0;
for(int i=0;i<s.size();i++){
result += extend(s,i,i,s.size());
result += extend(s,i,i+1,s.size());
}
return result;
}
};- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
代码流程
题目2：516 最长回文子序列
题目链接：最长回文子序列
对题目的理解
返回字符串s中最长回文子序列的长度，字符串s至少包含一个字符，且仅由小写字母组成。
动态规划
动规五部曲
1）dp数组及下标i的含义
dp[i][j]:[i,j]范围内的回文子序列的长度（左闭右闭）
2）递推公式
分为两种情况，s[i]==s[j] s[i]!=s[j]
当s[i]==s[j]时，dp[i][j]=dp[i+1][j-1]+2，加2是因为s[i]与s[j]相等，在原来回文子序列长度dp[i+1][j-1]的基础上加上2（这两个元素相同）
当s[i]!=s[j]时，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子序列的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列，因此要分为两种情况，考虑s[i]而不考虑s[j] 考虑s[j]而不考虑s[i]
1)考虑s[i]而不考虑s[j] dp[i][j]=dp[i][j-1]
2)考虑s[j]而不考虑s[i-1] dp[i][j]=dp[i+1][j]
dp[i][j]=max(dp[i][j-1],dp[i+1][j])
3）dp数组初始化
首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况，因为本题求的是最长回文子序列的长度，所以需要手动初始化一下，当i与j相同，那么dp[i][j]一定是等于1的，即：一个字符的回文子序列长度就是1。
根据递推公式，i一直加1，j一直减1，直到i==j
i==j时是初始化位置，指向了一个元素，一定是回文的，即dp[i][i]=1
！！！其他情况dp[i][j]初始为0就行，这样递推公式：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖，一定要初始化为0，这样才不会被覆盖
4）遍历顺序
根据递推公式，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，从下往上遍历，从左往右遍历，这两个for循环不可以颠倒，因为j依赖于i，因为字符串的范围是[i,j]，j一定是大于等于i的，一定是i在前，j在后。
5）打印dp数组
最终结果是dp[0][s.size()-1]
代码
class Solution {
public:
int longestPalindromeSubseq(string s) {
//定义dp数组
vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
//初始化dp数组
for(int i=0;i<s.size();i++) dp[i][i]=1;
for(int i=s.size()-1;i>=0;i--){
for(int j=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]);
}
}
return dp[0][s.size()-1];
}
};- 时间复杂度: O(n^2)
- 空间复杂度: O(n^2)
代码流程
