647.回文子串
题目链接：647. 回文子串 - 力扣（LeetCode）
感觉这道题的思路就是把字符串展开成二维数组，计算对每一个遍历到的回文子串进行计数，然后返回
1.dp数组的含义
dp[i][j]:在区间范围[i,j]的s子串是否是回文串，是则为true,不是为false
2.递推公式
当s[i] 与 s[j]不相等，直接略过不计数
当s[i] 与 s[j]相等
|、i 跟j指向同一个字符，比如a 是回文子串
||、i跟j相差为1，比如aa 是回文子串
|||、i跟j相差大于1，那就查看他前一个区间（dp[i + 1][j - 1]）的是否是回文串，如果同样是，那就计数
3.遍历顺序：
要推出dp[i][j]的值首先要知道dp[i + 1][j - 1]的值，所以遍历顺序得是从下到上 从左到右
这里的j一定大于等于i，所以遍历的时候j从i开始
class Solution {
public:int countSubstrings(string s) {vector<vector<bool>> dp(s.size(), vector(s.size(), false));int result = 0;for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j <= s.size() - 1; j++) {//j大于等于i,所以从i开始if (s[i] == s[j]) {if (j - i <= 1) {dp[i][j] = true;result++;} else if (dp[i + 1][j - 1]) {dp[i][j] = true;result++;}}}}return result;}
};516.最长回文子序列
题目链接：516. 最长回文子序列 - 力扣（LeetCode）
1.dp数组的含义：
dp[i][j]:字符串s在[i,j]范围内最长的回文子序列的长度为dp[i][j]
2.确定递推公式
当s[i]和s[j]相同的时候：dp[i][j]=dp[i+1][j-1]+2;
当s[i]和s[j]不相同的时候 就只考虑一个，要么考虑前面一个（dp[i][j-1]），要么考虑后面一个（dp[i][j-1])： dp[i][j]=max(dp[i][j-1],dp[i][j-1]);
3.dp数组的初始化
一个字符的回文子序列长度就为1
for(int i=0;i<s.size();i++){dp[i][i]=1;}4.确定遍历顺序
因为推导顺序是下面这样的，应该从下往上遍历，从左往右遍历，因为回文串长度j要大于等于i，
i等于j的时候已经初始化了，所以这里j从i+1开始遍历
然后我试了一下从j从1遍历，报错上说下面这个代码访问到无效数组
dp[i][j]=dp[i+1][j-1]+2;想了想，我觉得原因可能是：
比如字符有三个，i本来到2之后，因为j+1为3超出了数组大小，i就会直接结束了，但是这里j设置为1的话就不能直接结束了i会访问到3，访问到无效内存了
class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(),vector(s.size(),0));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;elsedp[i][j]=max(dp[i][j-1],dp[i+1][j]);}}return dp[0][s.size()-1];}
};