● 647. 回文子串
1.dp数组含义。
之前的题目，差不多都是求什么就怎么定义dp数组，最后返回dp的最后一个元素。但是这里如果定义一维数组dp[i]是[0,i]范围的回文子串的个数的话，怎么根据dp[i-1]得到dp[i]？发现很难找到递归关系，回文串需要固定两端来讨论判断。
所以需要二维数组。又：dp数组不统计个数，而是判断是否是回文子串的话，比较好推导递归关系：因为根据回文子串的定义，如果下标1、2、3组成的子串是回文串，那么只需要下标0和4的字符相等，就可以判定为回文子串。而统计个数的话还是需要比较中间所有的元素。
所以dp[i][j]：下标范围为[i,j]的子串是否回文，是为true，否为false。i、j都是闭区间，当i=j的时候就是单个字符，好初始化。
最后返回dp数组中值为true的个数。
2.递推公式。
参照上图，如果s[i]==s[j]而且中间的子串[i+1,j-1]是回文子串的话，那么[i,j]子串肯定是回文子串。这个图只考虑了i和j中间至少一个元素的情况，实际上在相等的条件下根据i和j的大小，得到dp[i][j]有3种情况：
①i==j：就一个字符，[i,j]是回文子串。
②j==i+1：2个字符，只要满足一个条件：s[i]==s[j]，就是一个回文子串。
③j>i+1：有≥2个字符，只要满足相等和dp[i+1][j-1]=true这两个条件的话，[i,j]就是回文子串。
所以dp[i][j]在上面3种情况中=true，其他的都是false，可以直接在初始化的时候设定。因为这里的条件且和或 的逻辑有点多，所以就分开写：
if(s[i]==s[j]){
if(j<=(i+1))//情况1和2
{
dp[i][j]=true;
count++;
}
if(i<n-1&&j>0&&dp[i+1][j-1]){//情况3
dp[i][j]=true;
count++;
}
}3.初始化。
在一开始定义dp数组的时候，我们就所有元素都初始化为false，到递推的时候再把每个元素更新为true。
注意情况①没有在初始化时设定，本来这个递推比较耗时间，在循环前面初始化的话有2个例子会超时。
4.遍历顺序。
这题的遍历顺序踩坑了，其实这个dp数组是一个对称矩阵，我们只需要统计对角线上true的个数加上：左下角或者右上角的true个数即可。再看定义的时候，我们说范围[i,j]内的，所以定为i<=j，即统计的是对角线+右上角的。又因为dp[i][j]是否为true取决于dp[i+1][j-1]，[i+1,j-1]是在[i,j]的左下角，说明到达i、j的时候，左下角的dp是需要更新了的。所以在i<=j的前提下：
（1）先列后行（先j后i）：
for(int j=0;j<n;++j){
for(int i=0;i<=j;++i){
}}（2）先行后列（先i后j）
for(int i=n-1;i>=0;--i){
for(int j=i;j<n;++j){
}}告诉我们遍历顺序需要简画一下dp数组的结构图。
5.打印。
代码如下。列优先的情况需要增加条件i<n-1 && j>0，行优先的话不需要添加。
class Solution {
public:
int countSubstrings(string s) {
int n=s.size();
int count=0;
vector<vector<bool>> dp(n,vector<bool>(n,false));
for(int j=0;j<n;++j){
for(int i=0;i<=j;++i){
if(s[i]==s[j]){
if(j<=(i+1))
{
dp[i][j]=true;
count++;
}
if(i<n-1&&j>0&&dp[i+1][j-1]){
dp[i][j]=true;
count++;
}
}
cout<<dp[i][j]<<" ";
}
}
return count;
}
};
● 516.最长回文子序列
● 动态规划总结篇
