1.回文子串
代码随想录 (programmercarl.com)
视频：动态规划，字符串性质决定了DP数组的定义 | LeetCode：647.回文子串_哔哩哔哩_bilibili
代码：
class Solution {
public:int countSubstrings(string s) {vector<vector<bool>>dp(s.size(),vector<bool>(s.size(), false));int result = 0;for(int i = s.size() - 1; i >= 0; i--){for(int j = i; j < s.size(); j++){if(s[i] == s[j]){if(j - i <= 1){dp[i][j] = true;result++;}else if(dp[i + 1][j - 1] == true){dp[i][j] = true;result++;}}}}return result;}
};note：
为了实现递推，拥有这种递推关系，最好是如果判断两端的元素相等，且两端内的字符串本身就是回文子串，就证明现在的子串也是回文子串，从而实现了递推关系。
dp数组的含义：dp[i][j]表示下标为[i,j]的字符串是否为回文子串
递推公式：
if(s[i] == s[j]){if(j - i <= 1){dp[i][j] = true;result++;}else if(dp[i + 1][j - 1] == true){dp[i][j] = true;result++;}
}dp数组的初始化：为了不影响计算，全部初始化为false
遍历顺序：根据递推公式，可知，我们要从下往上，从左往右遍历
2.最长回文子序列
代码随想录 (programmercarl.com)视频：动态规划再显神通，LeetCode：516.最长回文子序列_哔哩哔哩_bilibili
代码：
class Solution {
public:int longestPalindromeSubseq(string s) {vector<vector<int>> dp(s.size(),vector<int>(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;}else{dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);}}}return dp[0][s.size() - 1];}
};note：
dp数组的含义：下标为[i,j]的最长回文子序列的长度为dp[i][j]
递推公式：
if(s[i] == s[j]){dp[i][j] = dp[i + 1][j - 1] + 2;
}else{dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}注意子序列不必连续！
dp数组的初始化：将下标为[i,i]的元素全部初始化为1
遍历顺序：
根据递推公式，可知，我们要从下往上，从左往右遍历
3.动态规划总结
代码随想录 (programmercarl.com)