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

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

代码随想录

Python:

class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        dp[0] = [1]*n
        result = n
        for 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] = 1
                    result += 1
        return 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] = 1
        for 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] + 2
                else:
                    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];
    }
};

动态规划总结篇 

代码随想录