动态规划问题实例（3）：最长公共子序列/字串；最长回文子序列/子串

杨利霞

动态规划问题实例（3）：最长公共子序列/字串；最长回文子序列/子串
注：子序列不要求连续，子串要求连续。
1、最长公共子序列：
给定两个序列，求两序列的最长公共子序列，例子：

1.1、最优子结构：

1.2、伪代码：



1.3、C++代码：
#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

string getLCS(string s1, string s2)
{
//此部分获得最长值
         int m=s1.length()+1;
         int n = s2.length()+1;
         vector< vector<int> > c(m, vector<int>(n)); //计算长度
         vector< vector<int> > b(m, vector<int>(n)); // 字串遍历
         for(int i = 0;i<m;i++) { c[0] = 0; } // 初始条件（边界条件）
         for(int i = 0;i<n;i++) { c[0] = 0; } // 同上
         for(int i = 0;i<m-1;i++){
                for(int j = 0;j<n-1;j++){
                        if(s1 == s2[j]) {
                                c[i+1][j+1] = c[j] + 1;
                                b[i+1][j+1] = 1; // 1 表示相同
                        }
                        else if(c[j+1]>c[i+1][j]){
                                c[i+1][j+1] = c[j+1];
                                b[i+1][j+1] = 2; // 2 表示不同
                        }
                        else{
                                c[i+1][j+1] = c[i+1][j];
                                b[i+1][j+1] = 3; //  3表示不同
                        }
                }
        }
//此部分获得公共子序列
        stack<char> LCSans;
        for(i = m-1,j = n-1; i>=0 && j>=0; ;){
                if(b[j] == 1){
                        LCSans.push_back(s1);
                        i--;
                        j--;
                }
                else if(b[j] == 2)
            i--;
        else
                j--;
        }
// 此部分输出子序列
        while(!LCSans.empty()) {
       cout<<LCSans.top();
       LCSans.pop();
   }         
}

参考资料：动态规划解最长公共子序列(LCS)

2、最长公共子串：
把最长子序列else if判断语句换掉即可

string getLCS(string str1, string str2) {
        int m=s1.length()+1;
        int n = s2.length()+1;
        int maxlen = 0;
        int end;
        vector< vector<int> > c(m, vector<int>(n)); //计算长度
        for(int i = 0;i<m;i++) { c[0] = 0; } // 初始条件（边界条件）
        for(int i = 0;i<n;i++) { c[0] = 0; } // 同上
        for(int i = 0;i<m-1;i++){
                for(int j = 0;j<n-1;j++){
                        if(s1 == s2[j]) {
                                c[i+1][j+1] = c[j] + 1;
                        }
                        else {
                                c[i+1][j+1] = 0;
                        }
                        if(c[i+1][j+1]>maxlen){
                                maxlen = c[i+1][j+1];
                                end = i;
                        }
                }
        }
        return str1.substr(end - maxlen + 1, maxlen);
}

参考资料：求两个字符串的最长公共子串

3、最长回文子序列：
字符串中字符对称，称为回文，如字符串wabcdcbwq中wbcdcbw为回文子序列；bcdcb为回文子串。
解法：
将字符串s翻转后变s’，用公共子序列方法求解。

string longestPalindrome(string s) {
    if(s.length()==1) return s;//大小为1的字符串必为回文串
    string rev=s;//rev存放s反转结果
    string res;//存放结果
    std::reverse(rev.begin(),rev.end());
    if(rev==s) return s;
        //从此开始调用最长公共子序列算法。

4、最长回文子串：
4.1、动态规划版：
S表示字符串，i，j表示起始与结束位置。
初始条件（边界条件）：在长度小于2时，dp(i + 1, j -1)范围出错，所以长度为1，2为边界条件
a）dp = true(代码中用1表示了)
b）若S = S[i+1] 则dp[i+1] = true
状态转移方程：
a）若(dp(i + 1, j -1) == true && S == S[j]）则dp(i , j) = true
b）若(dp(i + 1, j -1) == false || S != S[j]）则dp(i , j) = false
class Solution {
public:
    string longestPalindrome(string s) {
        int len=s.size();
        if(len==0||len==1)
            return s;
        int start=0;//回文串起始位置
        int max=1;//回文串最大长度
        vector<vector<int>>  dp(len,vector<int>(len));//定义二维动态数组
        for(int i=0;i<len;i++)//初始化状态
        {
            dp=1; //单个元素是回文串
            if(i<len-1&&s==s[i+1]) //两个元素相同也是回文串
            {
                dp[i+1]=1;
                max=2;
                start=i;
            }
        }
        for(int l=3;l<=len;l++)//l表示检索的子串长度，等于3表示先检索长度为3的子串
        {
            for(int i=0;i+l-1<len;i++)
            {
                int j=l+i-1;//终止字符位置
                if(s==s[j]&&dp[i+1][j-1]==1)//状态转移
                {
                    dp[j]=1;
                    start=i;
                    max=l;
                }
            }
        }
        return s.substr(start,max);//获取最长回文子串
    }
};

参考资料：最长回文子串 C++解法 3：动态规划

4.2、中心扩展法：
中心扩散法怎么去找回文串？
从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。举个例子，str=acdbbdaa 我们需要寻找从第一个 b（位置为 3）出发最长回文串为多少。怎么寻找？
首先往左寻找与当期位置相同的字符，直到遇到不相等为止。
然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
最后左右双向扩散，直到左和右不相等。如下图所示：

每个位置向两边扩散都会出现一个窗口大小（len）。如果 len>maxLen(用来表示最长回文串的长度）。则更新 maxLen 的值。
因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下 maxLen 时的起始位置（maxStart），即此时还要 maxStart=len。
string LPS(string s)
{
        int maxstart = 0;
        int maxlen = 1;
        int start = 0;
        int len = 1;
        if(s.size()<=1) return s;
        for(int i = 0;i<s.size();i++){
                int l = i--;
                int r = i++;
                while(l>=0 && s[l] == s) { start = l; len++; l--}
                while(r<s.size() && s[r] == s) { len++; r++}
                while(l>=0 && r<s.size() && s[l] == s[r]) {
                        start= l;
                        l--;
                        r++;
                        len = len+2;
                }
                if(len > maxlen) { maxstart  = start; maxstart = start;}
                len = 1;
        }
        return s.substring(maxstart,maxlen);
}

参考资料：中心扩散法

总结：

1、动态规划关键：寻找最优子结构，即找到初始状态与状态转移方程。

————————————————
版权声明：本文为CSDN博主「夜空紫色」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_33726635/article/details/105933862





————————————————
版权声明：本文为CSDN博主「夜空紫色」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_33726635/article/details/105933862

chace

谢谢分享 写的很好