Leetcode516. 最长回文子序列

系统管理员 2022-01-05 08:07 240阅读 0赞

给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。

示例 1:  
输入:

"bbbab"  
输出:

4  
一个可能的最长回文子序列为 "bbbb"。

示例 2:  
输入:

"cbbd"  
输出:

2  
一个可能的最长回文子序列为 "bb"。

思路：动态规划。对问题的解决其实就是，把一个大问题分解成一个个小问题，这好像就是计算机较为普遍的解决办法。也是人脑的思考方向。怎么样去思考，当一维解决不了的时候，就二维，从二维的顶点往下，即自顶向下思考，自下而上写。

原先思考就是单纯的一维数组进行操作，可是不能保存从i...j的连续的状态，我就知道我错了。

但是参考了大牛的写法

状态 ：f(i,j)就代表了在一维数组中，从i到j过程中的最长回文子序列的长度，为什么这样能解决问题呢？？？答案在哪里？

转移方程：f(i,j)=f(i+1,j-1)+2.当s\[i\]==s\[j\]。s\[i\]!=s\[j\]时，f(i,j)=max(f(i+1,j),f(i,j+1)). //求f(i,j)时，要求出f(i+1,j)..f(i,j+1)..即循环的要从n-1-->0,再 从j-1 ..-..>j。

边界： f(i,i) = 1；其他为0. 即刚开始不知道从任意的i->j的值，但是i->i肯定是1.

根据边界的值，随转移方程的改变而改变，填充了二维数组。

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