本文主要是介绍代码随想录训练营day46|动态规划part13，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
回文子串
力扣题目链接
class Solution {
public://判断是否是回文bool isHuiwen(string &s, int i, int j){while(i <= j){if(s[i] != s[j])return false;i++;j--;}return true;}int countSubstrings(string s) {int len = s.length();vector<vector<int>> dp(len, vector<int>(len, 0));// dp[j][j+i]: j -> j+ifor(int i = 0; i < len; i++){for(int j = 0; j+i < len; j++){if(i == 0){dp[j][j+i] = 1;}else if(i == 1){dp[j][j+i] = dp[j][j+i-1] + dp[j+1][j+i];if(s[j] == s[j+i])dp[j][j+i]++;}else{dp[j][j+i] = dp[j][j+i-1] + dp[j+1][j+i] - dp[j+1][j+i-1];if(s[j] == s[j+i] && isHuiwen(s, j, j+i))dp[j][j+i]++;}}}return dp[0][len-1];}
};
最长回文子序列
力扣题目链接
class Solution {
public:int longestPalindromeSubseq(string s) {int len = s.length();vector<vector<int>> dp(len, vector<int>(len, 1));for(int i = 1; i < len; i++){for(int j = 0; i+j < len; j++){if(i == 1){if(s[j] == s[i+j]){dp[j][i+j] = 2;}}else{if(s[j] == s[i+j]){dp[j][j+i] = max(dp[j+1][j+i-1] + 2, max(dp[j+1][j+i], dp[j][j+i-1]));}else{dp[j][j+i] = max(dp[j+1][j+i], dp[j][j+i-1]);}}}}return dp[0][len-1];}
};
这篇关于代码随想录训练营day46|动态规划part13的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
