647. 回文子串

思路：

这道题的难点在于如何确定dp数组的含义以及递推关系。可以将i、j分别指向一个字符串的首位，如果两者是相同的就返回true，否则返回false，下一个字符串就可以在此字符串的基础上继续比较两个端点处的值即可。dp[i][j]：[i,j]区间内的字符串是否是回文字串，是的话为true，否则为false。递推关系：如果s[i]==s[j]，有三种情况：1、i==j，此时dp[i][j]一定是true，2、如果j-i==1，此时也一定是true，3、如果j-i>1，需要考虑dp[i+1][j-1]（里面的一个字符串）是否为true，是的话dp[i][j]才是true。初始化：为了递推关系的简单，所有元素初始化为false。遍历顺序：根据递推关系，i需要从后向前，j从前向后。

代码：

class Solution {

public:

    int countSubstrings(string s) {

        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));

        int res=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;

                        res++;

                    }else

                    {

                        if(dp[i+1][j-1]==true)

                        {

                            dp[i][j]=true;

                            res++;

                        }

                    }

                }

            }

        }

        return res;

    }

};

516. 最长回文子序列

思路：

这道题的解题思路与上面一道题大致相同，dp[i][j]：区间[i,j]内最长回文子序列的长度是dp[i][j]。递推关系：如果s[i]==s[j]，最长子序列的长度dp[i][j]=dp[i+1][j-1]+2；如果不相等，那就比较s[i]与s[j-1]以及s[i+1]与s[j]，取二者的最大值即可。初始化：所有元初始化为0，同时由递推关系可知，i==j的情况是无法计算的，所以还要额外初始化一下。递推关系：i从大到小，j从小到大。

代码：

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

    }

};