本文主要是介绍算法学习 | day49/60 回文子串/最长回文子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目打卡
1.1 回文子串
题目链接：. - 力扣（LeetCode）
class Solution {
public:int countSubstrings(string s) {// vector<bool> dp;// // 这里想在初始化之外进行构造，就需要使用 assign 函数// if(s.size()&1 == 0) dp.assign(s.size()/2,false);// else dp.assign(s.size()/2+1,false);// if(s.size()&1 == 1) dp[0] = true;// else{// if(s[s.size()/2 - 1] == s[s.size()]) dp[0] = true;// }// for(int i = 1, j = s.size()&1 ? :s.size()/2+1)// return 1;// 在[i,j]之间的子串是不是回文串vector<vector<bool>> dp(s.size(),vector<bool>(s.size(), false));int res= 0;// 这里因为取值的时候是从左下转移过来的，所以不能从前向后遍历，不然的话会取到的值可能是错的for(int i = s.size() - 1; i >= 0;i--){// for(int i = 0; i < s.size();i++){for(int j = i; j < s.size();j++){if(s[i] == s[j]){if(j - i <= 1){dp[i][j] = true;res++;}else{if(dp[i+1][j - 1]){dp[i][j] = true;res++;}}}}}for(int i = 0 ; i < s.size();i++){for(int j = 0; j < s.size();j++){cout << dp[i][j] << " "; }cout << endl;}return res;}};
这里和之前动态规划类题目都不太一样，这个题目的dp数字的定义主要是考虑了回文这个结构的特殊性，直接看的答案解析，看懂了其实再来理解这个题目就不是很难了。
动态规划转移的方程，重要的是要理解为什么这个转移的方向来自左下角，这也决定了后面的遍历顺序，必须是从i的最后面向前遍历，否则就会是没有填充的数值进行的递推。
1.2 最长的回文子串
题目链接：. - 力扣（LeetCode）
class Solution {
public:int longestPalindromeSubseq(string s) {// [i,j]之间最长的回文子序列vector<vector<int>> dp(s.size(),vector<int>(s.size(), 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) dp[i][j] = 1;else if(j - i == 1) dp[i][j] = 2;else dp[i][j] = dp[i + 1][j - 1] + 2;}else dp[i][j] = max({dp[i + 1][j - 1], dp[i][j-1], dp[i+1][j]});}}// for(int i = 0; i < s.size();i++){// for(int j = 0 ; j< s.size();j++){// cout << dp[i][j] << " ";// }// cout << endl;// }return dp[0][s.size() - 1];}
};和上面的题目稍微有一点区别，但是转移的思路其实还是一致的，主要在于处理递推的时候，需要注意当前两个指针不相等的时候，递推的方法就需要对之前的内容进行处理。
这篇关于算法学习 | day49/60 回文子串/最长回文子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
