题目描述：
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。示例1：
输入:"abc"
输出:3
解释:三个回文子串: "a", "b", "c".示例2：
输入:"aaa"
输出:6
说明:6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
方法1：动态规划
本题可使用动态规划方法来解决。
设字符串长度为n，则新建布尔类型数组dp[n][n]来保存相应位置是否是回文字符串。其中dp[i][j]代表字符串从第i个字符到第j个字符组成的子串是否为回文字符串。
当i==j时，显然有dp[i][j] = true.
当i!=j时，则有
这是因为若i到j组成的子串为回文字符串时，其两端加上相同的字符仍为回文字符串。
在处理完所有子串后，对回文字符串进行统计即可。
具体代码如下：
int countSubstrings(string s) {
int n = s.length();
vector<bool> t(n,false);
vector<vector<bool>> dp(n,t);
int res = 0;
for (int j = 0; j < n; j++) {
for (int i = 0; i <= j; i++) {
if (i == j) {
dp[i][j] = true;
} else {
dp[i][j] = s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]);
}
}
}
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
if(dp[i][j])
{
res++;
}
}
}
return res;
}
其中要注意i和j的顺序，由于在计算dp[i][j]时，需要dp[i+1][j-1]的值，则必须保证当计算dp[i][j]时，其左下侧的数值已经计算完毕。因此应按列进行计算。
方法二：奇偶扩展
回文字符串可以分为长度为奇数和长度为偶数2种情况。
当长度为奇数时，字符串由中心的一个字符向前后扩展，若前后字符串相同，则其扩展的字符串仍为回文字符串。
当长度为偶数时，字符串由两个相同的连续字符向前后扩展，若前后字符串相同，则其扩展的字符串仍为回文字符串。
int countSubstrings(string s) {
int n = s.length();
int res = 0;
for(int i=0;i<n;i++)
{
int start = i,end = i;
while(start >= 0 && end < n)
{
if(s[start] == s[end])
{
res++;
start--;
end++;
}
else
{
break;
}
}
start = i;
end = i + 1;
while(start >= 0 && end < n)
{
if(s[start] == s[end])
{
res++;
start--;
end++;
}
else
{
break;
}
}
}
return res;
}
