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

647. 回文子串

文字讲解：代码随想录

视频讲解：动态规划，字符串性质决定了DP数组的定义 | LeetCode：647.回文子串_哔哩哔哩_bilibili

解题思路

1.dp[i][j]         [i,j]子串是否是回文的           是则返回true，不是则返回false

2.递推公式

if(s[i] == s[j])                        1.i==j    指向同一个元素，那么是回文子串

 {      if(j-i<=1)  {dp[i][j] =true; result +=1}     2.i,j相差1   aa 也是回文子串

          else if(dp[i+1][j-1]==true)  {dp[i][j] =true; result +=1}    3. j -i > 1       要看i+1,j-1是否是回文子串

}

3.初始化

全都为false，默认都不是回文子串，根据递推来改区间

4.遍历顺序

从左往右，从下往上

class Solution {
public:
    int countSubstrings(string s) {
            int n = s.size();
            int result = 0;
            vector<vector<int>> dp(n,vector<int>(n,0));
            for(int i = n-1 ; i >= 0 ; i--)         //从下往上
            {
                for(int j = i ; j < n ; j++)        //从左往右，我们要从i开始扩散去判断
                {
                       if(s[i]==s[j])
                       {
                            if(j-i<=1)
                            {
                                dp[i][j] = 1;
                                result+=1;
                            }
                            else if(dp[i+1][j-1])           //如果两端是相同的，就同时回缩，看里层是不是回文的
                            {
                                dp[i][j]=1;
                                result+=1;
                            }
                       }
                }
            }
            return result;
    }
};

516.最长回文子序列

文章讲解：代码随想录

视频讲解：动态规划再显神通，LeetCode：516.最长回文子序列_哔哩哔哩_bilibili

解题思路

1. dp[i][j]                [i,j]区间内的回文子序列的长度

2.if(s[i]==s[j])            dp[i][j] = dp[i+1][j-1] + 2       //在内层的回文子序列长度+2

else                         dp[i][j] = max(dp[i-1][j], dp[i][j-1])  //如果不相等，考虑单独包含一个元素的情况，[i,j-1]的情况，和[i+1,j] 这两个区间的最大回文子序列

3.初始化

看根基，i和j相同的情况下，应该初始化为1

4.遍历顺序

推导方向，从左往右，从下往上

for(i = size()-1)

        for(j = i+1 )  j=i已经初始化过了

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

动态规划总结

https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E6%80%BB%E7%BB%93%E7%AF%87.html