算法D57 | 动态规划17 | 647. 回文子串 516.最长回文子序列 动态规划总结篇

647. 回文子串   

动态规划解决的经典题目，如果没接触过的话，别硬想 直接看题解。

代码随想录

Python:

class Solution:def countSubstrings(self, s: str) -> int:n = len(s)dp = [[0]*n for _ in range(n)]dp[0] = [1]*nresult = nfor i in range(1, n):for j in range(i,n):if dp[max(0, i-2)][j-1]==1 and s[j]==s[j-i]:dp[i][j] = 1result += 1return result

C++:

class Solution {
public:int countSubstrings(string s) {vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));dp[0] = vector<int>(s.size(), 1);int result = s.size();for (int i=1; i<s.size(); i++) {for (int j=i; j<s.size(); j++) {if (s[j]==s[j-i] && dp[max(0, i-2)][j-1]==1) {dp[i][j] = 1;result++;}}}return result;}
};

516.最长回文子序列 

647. 回文子串，求的是回文子串，而本题要求的是回文子序列， 大家要搞清楚两者之间的区别。 

代码随想录

Python:

回文子串是连续的，回文子序列是可以不连续的。回文子序列要比求回文子串简单一点，因为情况少了一点，本题的难点在于根据递推关系确定逆向更新。

class Solution:def longestPalindromeSubseq(self, s: str) -> int:n = len(s)dp = [[0]*n for _ in range(n)]for i in range(n):dp[i][i] = 1for i in range(n, -1, -1):for j in range(i+1,n):if s[i]==s[j]:dp[i][j] = dp[i+1][j-1] + 2else:dp[i][j] = max(dp[i+1][j], dp[i][j-1])return dp[0][n-1]

C++:

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];}
};

动态规划总结篇 

代码随想录