Day57 动态规划part17 647. 回文子串 516. 最长回文子序列

本文介绍: 647. 回文子串 516. 最长回文子序列

Day57 动态规划part17 647. 回文子串 516. 最长回文子序列

647. 回文子串

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size()+1,vector<bool>(s.size()+1,false)); //dp[i][j]含义[i,j]范围内的字符串是否为回文
        int result = 0; //记录回文串个数
        for(int i = s.size()-1;i>=0;i--){
            for(int j =i; j<=s.size()-1;j++){
                if(s[i]==s[j]) {
                    if(j-i<=1) {    //单个字符是回文串，两个字符相等，也是回文串
                        result++;
                        dp[i][j] = true;
                    }else if(dp[i+1][j-1]==true){//第三种情况
                        result++;
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
            }
        }
        return result;
    }
};

516. 最长回文子序列

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));   //dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

        for(int i = s.size()-1;i>=0;i--){
            for(int j = i; j<=s.size()-1;j++){
                if(s[i]==s[j]) {
                    if(i==j) dp[i][j] = 1;
                    else 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];
    }
};