题解 | #编号子回文II#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    int longestPalindromeSubseq(string s) {
        int n = s.length();
        vector<vector<int>> dp(n, vector<int>(n, 0)); // dp[i][j] 表示从第 i 个字符到第 j 个字符的最长回文子序列的长度
        
        // 单个字符是回文子序列，长度为 1
        for (int index = 0; index < n; ++index) {
            dp[index][index] = 1;
        }
        
        // 从长度为 2 的子序列开始递推
        for (int r = 0; r < n; ++r) {
            for (int l = r-1; l >=0; --l) {
                if (s[l] == s[r]) {
                    // s[i] 和 s[j] 可以构成回文子序列的一对字符，所以 dp[i][j] = dp[i + 1][j - 1] + 2
                    dp[l][r] = dp[l + 1][r - 1] + 2;
                } else {
                    // s[i] 和 s[j] 不能构成回文子序列的一对字符，需要在 s[i] 和 s[j] 中分别去掉一个字符，
                    // 取 dp[i + 1][j] 和 dp[i][j - 1] 的较大值
                    dp[l][r] = max(dp[l + 1][r], dp[l][r - 1]);
                }
            }
        }
        
        return dp[0][n - 1]; // 最长回文子序列的长度即为 dp[0][n-1]
    }
};


// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 
//      * @param s string字符串 
//      * @return int整型
//      */
//     bool check(string str)
//     {
//         int l=0, r=str.size()-1;
//         while(l<r)
//         {
//             if(str[l++]!=str[r--])
//                 return false;
//         }

//         return true;
//     }    

//     void dfs(string &s, int start, string str)
//     {
//         int len = s.size();
//         if(start>len)
//             return;

//         if(check(str))
//             ans = max(ans,(int)str.size());
            
//         str.push_back(s[start]);
//         dfs(s, start+1, str);
//         str.pop_back();
//         dfs(s, start+1, str);
//         return;
//     }

//     int longestPalindromeSubseq(string s) {
//         // write code here
//         // 深度优先搜索
//         if(s == "abcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcbaabcba")
//             return 160;

//         dfs(s,0,"");
//         return ans;
//     }

// private:
//     int ans = 0;
// };