博客

1. dp数组：dp[i][j]表示区间i~j之间是否为回文串
2. 递推公式：
   
   当s[i] == s[j]时，
   
   若i == j，则此时肯定为回文子串，dp[i][j] = true;
   
   若j – i = 1，则此时也为回文子串，dp[i][j] = true;
   
   若j – i > 1，则需要判断i + 1 ~ j-1是否为回文串，即dp[i][j] = dp[i+1][j-1]是否为true；
   
   当s[i] != s[j]，则 dp[i][j] =false；
   
   3.初始化， dp[i][j]初始化为false；
3. 遍历顺序，由递推公式可知dp[i][j]需由dp[i+1][j-1]推导而来。则遍历顺序为从下到上，从左到右。这样才可以保证dp[i+1][j-1都是经过计算了的。
4. 推导dp数组。dp数组有几个true，就有几个回文子串。
   
   注意dp[i][j]的定义，可以知道j一定是大于等于j的，故二维数组只有上半部分被计算了。

class Solution {
public:
    int countSubstrings(string s) {
        //dp[i][j]表示区间i~j是否为回文子串
        vector<vector<bool> > dp(s.size() + 1, 
        vector<bool>(s.size() + 1));

        int res = 0;
        

        for(int i = s.size(); i >= 1; i--){
            for(int j = i; j <= s.size(); j++){
                if(s[i-1] == s[j-1]){
                    if(j - i <= 1){
                        dp[i][j] = true;
                        res++;
                    }
                    else{
                        if(dp[i+1][j-1]){
                            dp[i][j] = true;
                            res++;
                        }
                    }
                    
                }
                else{
                    dp[i][j] = false;
                }
            }
        }
        return res;
    }

        
};

1. dp[i][j]: 区间i ~ j内的最长回文子串长度
2. 递推公式：
   
   若s[i] == s[j]
   
   则dp[i][j] = dp[i + 1][j- 1] + 2
   
   若s[i] ！= s[j]
   
   则dp[i][j] = max(dp[i][j-1], dp[i+1][j])

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int> > dp(s.size() + 1, 
        vector<int>(s.size() + 1, 0));

        for(int i = 1; i <= s.size(); i++)
            dp[i][i] = 1;
        

        for(int i = s.size()-1 ; i >= 1; i--){
            for(int j = i + 1 ; j <= s.size(); j++){
                if(s[i-1] == s[j-1]){
                    dp[i][j] = dp[i+1][j-1] +
                          2; 
                }
                else{
                    dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
                }
            }
        }
        return dp[1][s.size()];
    }
};