算法训练营day57_动态规划（3.18提前写）

647.回文子串

求一个字符串中有多少个回文子串；

与以往不同，这里还套用前i个的话，找不到与i-1的递推关系；

• f(i,j)表示[i,j]子串是否为回文子串；

• 转移；如果s[i]==s[j]，看[i+1,j-1]，因为可能有交叉，需要分类讨论；

  ​ 如果i-j只有<=2个字符，那么肯定是回文的；

  ​ 如果i-j有>=3个字符，看f[i+1] [j-1]；

• 初始化；全为false;

• **遍历顺序；本题遍历顺序有讲究的！**之前习惯了从左到右；遍历顺序关键要把小状态提前算出来，故本题i需要倒序，j从左到右，还有个坑点就是j必须从i开始，因为区间[i,j]；

class Solution {
public:
    int countSubstrings(string s) {
        int n=s.size();
        vector<vector<bool>> f(n+1,vector<bool> (n+1,false));
        s=" "+s;
        int ans=0;
        for(int i=n;i>=1;i--){
            for(int j=i;j<=n;j++){
                if(s[i]==s[j]){
                    if(j-i<=1){f[i][j]=true;ans++;}
                    else{
                        if(f[i+1][j-1]){f[i][j]=true;ans++;}
                    }
                }
            }
        }
        return ans;
    }
};

516.最长回文子序列

本题是最长回文子序列，与上题有些差别；状态表示+状态转移都想出来了，关键是初始化没想出来；

• f(i,j)表示[i,j]子序列最长回文子序列的 长度；

• 转移；如果s[i]==s[j]，=[i+1,j-1]+2；

  ​ 比较(i+1,j)与(i,j+1)；

• **初始化；比较关键，**全为false;i到j只有一个的话，初始化为true；

• **遍历顺序；**本题是从左下转移右上，故i是倒序，j是顺序；

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n=s.size();
        s=" "+s;
        vector<vector<int>> f(n+1,vector<int>(n+1,0));
        for(int i=1;i<=n;i++) f[i][i]=1;
        for(int i=n;i>=1;i--){
            for(int j=i+1;j<=n;j++){
                f[i][j]=max(f[i+1][j],f[i][j-1]);
                if(s[i]==s[j]) f[i][j]=max(f[i][j],f[i+1][j-1]+2);
            }
        }
        return f[1][n];
    }
};