代码随想录算法训练营第57天|647.回文子串 516.最长回文子序列

647.回文子串

        唉这道题让我用dp我是会不了一点啊啊啊，这道题的dp[i][j]表示从给定字符串的第i个位置到第j个位置这一部分的字符串是不是一个回文串，如果s[i]==s[j]，并且j-i<=1，那么dp[i][j]=true,如果j-i>=1，那么如果dp[i+1][j-1]==true的话，那么dp[i][j]=true，从第二种情况来看，我们可以看出本题的遍历顺序是从下往上，从左往右，因为要知道dp[i+1][j-1]的值，是处在当前位置的左下方，所以可以知道遍历顺序。

https://leetcode.cn/problems/palindromic-substrings/submissions/512191445/

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>>dp(s.size(),vector<bool>(s.size(),false));
        int result=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<=1)
                    {
                        dp[i][j]=true;
                        result++;
                    }
                     else if(dp[i+1][j-1]==true)
                    {
                        dp[i][j]=true;
                        result++;
                    }
                }
            }
        }
        return result;
    }
};

516.最长回文子序列

        这道题和上面那道题有点像，但我还是不能真正理解，所以我会延续上一道题的思路把dp[i][j]赋值成bool类型，但是应该赋值成int类型，dp[i][j]表示从给定数组的第i个位置到第j个位置的字符串的最长回文序列的个数，假如说s[i]==s[j],那么dp[i][j]=dp[i+1][j-1]+2,假如说s[i]!=s[j]，那么dp[i][j]=max(dp[i+1][j],dp[i][j-1])，就是选取最左边和最右边的元素中的一个（因为根据题目描述是可以删除一个的）。从转移方程可以知道遍历顺序是从下到上，从左到右。

https://leetcode.cn/problems/longest-palindromic-subsequence/

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][j-1],dp[i+1][j]);
                }
            
             }
        }
        return dp[0][s.size()-1];
    }
};