博客

1.最长回文子串

2.

前言

动态规划回文串系列一直是我的一个痛点,今天上午看了书,本以为已经完全看懂了,结果下午闭书敲代码,敲了一下午还没有搞定,哎,果然代码不是靠看懂的,中间思考过程的艰深,只有敲过了代码才能感受到.

思路

dp五部曲:

1)确定dp[i][j]含义,这一步最重要,也是最难抉择的,为什么说最难抉择呢?到底dp[i][j]表示以下标[i,j]的字符串还是下标[i+1][j-1]的字符串呢?还是下标[i-1][j-1]的字符串呢?我们选择下标[i][j]的字符串含义,因为这样方便后续处理

2)递推公式:

第一题:

if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1]+2,否则dp[i][j]=max(dp[i+1][j],dp[i][j+1])  //表示选择更长的序列

第二题:

if(s[i]==s[j]) 三种情况讨论:

①.i==j

②.j-i==1 ,eg:aa

③.j-i>1    我们需要通过判断dp[i+1][j-1]来判断dp[i][j]是不是回文串

3)初始化

第一题:

我们对除了对角线上dp[i][i]的元素初始为1,表示自己到自己算一个长度,剩下的长度为0

第二题:

我们对对角线的初始化为true,剩下的为false

4)遍历顺序:

这两道题较为值得一说的就是遍历顺序:从下到上,从左到右遍历,因为我们对于dp[i][j]的判断是需要依赖于dp[i+1][j-1]的.

5)重点:

是呀!确定了遍历了顺序,可是如何保证那些繁琐的+1,-1操作不会overflow呢



?

很多人稀里糊涂地AC了,以为就完了,但是问他对于边界的处理逻辑,他可能回答不上来.

第一道题:

因为j>=i,所以我们只需要填满右上角就好,我们为了防止[i+1][j-1]越界,其实就是防止[0][0]和[size-1][size-1]两个位置越界,那么怎么防止呢?我们提前初始化好了[i][i]上的元素,所以在设置 j 时不需要设置为i,而是设置为i+1,这样就巧妙避开了那两个会下标越界的位置.

第二道题:

这道题比较特殊,因为分类讨论了(你问我为啥要对s[i]==s[j]的情况分类讨论? 很简单,因为它们相同,相邻,至少相隔一个三种情况中前两个情况是一样的,第三种情况需要判断它的左下角元素[i+

1][j-1]后才能对dp[i][j]进行赋值为true操作,比如abca,你看s[0]==s[3],但是dp[1][2]为false,所以dp[0][3]不能设置为true(我们初始化为false,所以不用操作)),所以在对j-i<=1的情况dp[i][j]=true,res++;这种情况一定是合法的,而不用去管dp[i+1][j-1](这种情况只有在j-i>1的情况下才去管,而一个矩阵只有在[0][0],[size-1][size-1]两个位置会下标越界)

第一代码:

#include<string>
#include<vector>
using namespace std;
#include<string>
#include<vector>
using namespace std;

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int size = s.size();
        vector<vector<int>> dp(size , vector<int>(size , 0));
        for (int i = 0; i < size; ++i)    dp[i][i] = 1;
        for (int i = size - 1; i >= 0; --i) {
            for (int j = i + 1; j < size; ++j) {      //这里设置为j=i+1,就不用考虑边界问题了
                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][size - 1];
    }
};

第二代码:

class Solution {
public:
    int countSubstrings(string s) {
        //dp[i][j]表示[i,j]是不是回文串
        /*
        * if(s[i]==s[j])
        * 分三种情况:
        *   ①.i==j
        *   ②.j-i==1
        *   ③.j-i>1
        * 
        */
        int size = s.size();
        int res = 0;
        vector<vector<bool>> dp(size,vector<bool>(size, false));
        for (int i = 0; i < size; ++i)  dp[i][i] = true;
        for (int i = size-1; i >= 0; --i) {
            for (int j = i; j < size; ++j) {
                if (s[i] == s[j]) {
                    if (j - i <= 1) { dp[i][j] = true; res++; }
                    else if (dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        res++;
                    }
                }
            }
        }
        return res;
    }
};