最长回文子序列---DP

2021年09月16日 阅读数:2
这篇文章主要向大家介绍最长回文子序列---DP,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

问题描述

给定一个字符串s,找到其中最长的回文子序列。能够假设s的最大长度为1000html

解题思路

1.说明

首先要弄清楚回文子串和回文子序列的区别,若是一个字符串是“bbbab”,那么它的回文子串为“bbb”,可是其回文子序列是“bbbb”,这是由于回文子序列中能够相隔字符,不必定要连续。数组

2.思路

定义dp数组的含义。这里咱们定义一个二维数组dpspa

dp[i][j]表示字符串str从i到j的字符串中最长回文子序列的长度。code

假设咱们如今已经知道dp[i+1][j-1]的值,那么dp[i][j]的值只须要判断s[i]和s[j]是否相等便可。htm

若是s[i]=s[j],那么dp[i][j]=dp[i+1][j-1]+2,直接加2便可。blog

若是s[i]!=s[j],说明s[i]和s[j]至少是不在这个回文序列的,代表这时的dp[i][j]只需取二者之间的最大值便可,那么dp[i][j]=Max(dp[i][j-1],dp[i+1][j])。字符串

3. 举例说明

例如字符串“bbbab”,在建立数组以前,能够先将以下矩阵的部份内容填好,由于dp[i][i]一个字符便可构成一个回文序列,因此有dp[i][i]=1。同时,dp[i][j](i>j)=0;即不存在。table

而后能够从下往上来计算。class

i\j 0 1 2 3 4
0 1  2  2  4
1 0 1  2  3
2 0 0 1  3
3 0 0 0 1  1
4 0 0 0 0 1

 

填满表格最后的一个数即为回文子序列最长的长度。返回dp[o][4]便可。二维数组

3. 代码

int longestPalindromeSubseq(char * s){
    int N=strlen(s);
    int dp[N][N]; //dp[i][j]表示从i到j回文子序列的长度
    for(int i=0;i<N;++i){
        for(int j=0;j<N;++j){
            if(i==j) dp[i][j]=1;
            else dp[i][j]=0;
        }
    }
    for(int i=N-1;i>=0;--i){
        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]=fmax(dp[i][j-1],dp[i+1][j]);
        }
    }
    return dp[0][N-1];

}