【C++编程能力提升】

一、647 回文子串

题目链接：647 回文子串

核心：求解回文子串的数目时，dp数组可定义为二维数组，表示字符串s的[i,j]区间范围内是否为回文子串，若是则dp值为true，更新回文子串的数目，否则dp值为false。
确定d[i][j]值（即[i,j]区间是否为回文子串）时，必然在s[i]==s[j]的情况下，否则一定不是回文子串。而在s[i]==s[j]时也需要区分不同情况，其一是i=j，说明只有一个元素，那么必然是回文子串；其二是i+1=j，说明只有两个元素且相同，也必然是回文子串；其三是j-i>1的情况，需要根据dp[i+1][j-1]的值确定dp[i][j]是否为回文子串。
此外遍历顺序也需要注意，因为递推公式涉及到dp[i+1][j-1]，那么一定是从下到上，从左到右遍历。

    int countSubstrings(string s) {
    //dp[i][j]表示以i，j为区间的字符串是否为回文子串，若是则dp[i][j]=true
    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)
        {//区间范围是[i,j]，因此j从i开始遍历
            if(s[i]==s[j])
            {
                if(j-i<=1)
                {//要么是j==i，要么是j=i+1，比如：a和aa，两类情况都是回文子串
                    res++;
                    dp[i][j]=true;
                }
                else if(dp[i+1][j-1])
                {//j-i>1时，只有在[i+1,j-1]区间范围是回文子串时，[i,j]才是回文子串
                    res++;
                    dp[i][j]=true;
                }
            }
        }
    }
    return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

二、516 最长回文子序列

题目链接：516 最长回文子序列

核心：计算最长回文子序列的长度时可定义dp[i][j]为[i,j]区间内的回文子序列长度，那么有两种情况，其一是s[i]==s[j]，此时回文子序列长度依赖于dp[i+1][j-1]；其二是s[i]!=s[j]，此时包含i和j的区间无法构成回文子序列，需要考虑包含i或者包含j构成的区间的回文子序列。
遍历顺序是从下到上，从左到右，因此最长回文子序列的值在dp数组的第一行最后一列。

    int longestPalindromeSubseq(string s) {
    //dp[i][j]表示i,j区间内的回文子序列长度
    vector<vector<int>> dp(s.size(),vector<int> (s.size(),0));
    for(int i=0;i<s.size();++i)
        dp[i][i]=1;  //一个元素构成的回文子序列长度是1
    for(int i=s.size()-1;i>=0;i--)
    {//遍历行时一定是从下到上
        for(int j=i+1;j<s.size();++j)
        {//遍历列时是从左到右,且从i+1开始（因为dp[i+1][j-1])
            if(s[i]==s[j])
                dp[i][j]=dp[i+1][j-1]+2;  //i和j能与[i+1,j-1]构成回文子序列
            else   //i和j不能与[i+1,j-1]构成回文子序列，可以取s[i+1]或者s[j-1]
                dp[i][j]=max(dp[i][j-1],dp[i+1][j]);  //为啥[i+1,j]或[i,j-1]是回文子序列？
        }
    }
    return dp[0][s.size()-1];  //最终第一行最后一列的值是最长回文子序列的长度。
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17