动态规划终于要刷完了！虽然动规五部曲已经烂熟，也刷了有二三十题经典的动态规划题，但是自己实际做题时未必能用的很好，一方面是有些题目实在很难想到用动规解题，另一方面是即使想到动态规划，往往卡在状态的定义和状态转移上（更别说一些细节了，比如初始化），反复刷经典题目其实只是在学习方法论，关键还是得活学活用，毕竟做题时不会预先告诉你这时什么类型的题可以套什么思路~
LeetCode 647 回文子串
一开始看题会如讲解所说的陷入一个误区，就是用编辑距离的方式定义dp数组，dp[i]和dp[i-1]之间不知道怎么构造状态转移。回文的性质使得解题需要打开思路，如果一个字符串中首尾字符相同，去掉首尾字符后的子串如果是回文的，那么整个字符串就是回文的。这里对于单个字符串也要使用二维的dp数组，dp[i][j]定义为s[i : j]（左闭右闭区间）是否为回文串，遍历i和j就枚举了子串的首尾位置，又因为j要大于等于i（等于时为单个字符，也是回文的），遍历时需要将j初始化为i。
定义好dp数组后，状态转移上，s[i]和s[j]不相等，s[i : j]必然不能构成回文子串；如果s[i]==s[j]，dp[i][j]的结果取决于dp[i+1][j-1]（除去s[i]和s[j]之后的子串是否为回文子串），从而也决定了遍历顺序上，i 需要倒序遍历，j 则可以正序遍历。
class Solution {
public:
int countSubstrings(string s) {
int n = s.length();
vector<vector<bool>> dp(n, vector<bool>(n, false));
int result = 0;
for(int i = n - 1; i >= 0; i--){
for(int j = i; j < n; j++){
if(s[i] == s[j]){
if(j - i <= 1){
dp[i][j] = true;
result++;
}
else if(dp[i+1][j-1]){
// 遍历顺序决定了i+1不会越界
dp[i][j] = true;
result++;
}
}
// else dp[i][j] = false; 初始化已经为false，可以不写
}
}
return result;
}
};动态规划做多了，也没想过用双指针。双指针的时间复杂度也是O(n^2)，但省去了dp数组的空间复杂度，主要方法就是以某一个或两个字符为中心点向左右遍历，判断能否构成回文（自己懒得写，贴上代码随想录的C++实现）：
class Solution {
public:
int countSubstrings(string s) {
int result = 0;
for (int i = 0; i < s.size(); i++) {
result += extend(s, i, i, s.size()); // 以i为中心
result += extend(s, i, i + 1, s.size()); // 以i和i+1为中心
}
return result;
}
int extend(const 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;
}
};LeetCode 516 最长回文子序列
题目链接：516. 最长回文子序列 - 力扣（Leetcode）
相比于上一题，子序列不要求连续，定义区间s[i: j]之间的最长回文子序列的长度为dp[i][j]，如果s[i]==s[j]，dp[i][j] = dp[i-1][j-1]+2；如果s[i] != s[j]，也就是不能可以只在s[i-1: j-1]的基础上在左边加上s[i]，或者在右边考虑加上s[j]，看是否能让回文子序列的长度增加，二者取最大即可。
遍历顺序和回文子串中的类似，由于dp数组含义不同，这里dp数组还要做额外的初始化，将dp[i][i]均初始化为1，因为在遍历过程中无法遍历到单个字符的情况：
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.length();
vector<vector<int>> dp(n, vector<int>(n));
for(int i = 0; i < n; i++) dp[i][i] = 1;
for(int i = n - 1; i >= 0; i--){
for(int j = i + 1; j < n; j++){
// j = i的情况已经初始化，j从i+1开始遍历
if(s[i] == s[j]){
dp[i][j] = dp[i + 1][j - 1] + 2;
}
else{
// 第一项：在右边加入s[j]；第二项：在左边加入s[i]；
dp[i][j] = max(dp[i + 1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1]; // s[0 : n - 1]之间的最长回文子序列的长度（左闭右闭区间）
}
};这一题对于我来说不是那么好想，因为连续的限制更多，状态转移其实会更明确一些。