近水楼台先得月
向阳花木易为春
因为个肺炎疫情，在家待了半个月了，准备开始继续刷题了，打了一周的只狼，打铁的感觉真不错23333。
说回到这道题，C++，动态规划。
回文串的题，用dp来解就是最简单和最容易理解的套路。
定义一个动态数组dp，dp[i][j]表示下标从i到j组成的子串是不是回文串，我们直接两层循环，遍历dp数组的所有值，如果s[i] == s[j]成立，会得到转移方程：
然后就是注意一下：
- 每个单字符都是一个回文子串
- 相同字符挨在一起也是一个回文子串
思路简单，代码写的也就很简单了：
class Solution {
public:
int countSubstrings(string s) {
int ans = 0;
vector<vector<bool>> dp(s.length(), vector<bool>(s.length()));
for (int i = 0 ; i < s.length(); i++) {
dp[i][i] = true;
ans++;
if (i < s.length() - 1 && s[i] == s[i + 1]) {
dp[i][i + 1] = true;
ans++;
}
}
int l = 3;
for (; l <= s.length(); l++) {
for (int i = 0; i + l - 1 < s.length(); i++) {
int j = i + l - 1;
if (s[i] == s[j]) {
if (dp[i + 1][j - 1]) {
dp[i][j] = true;
ans++;
}
}
}
}
return ans;
}
};
