数据结构：LDP最大回文子序列

女爷i 2022-05-31 12:54 121阅读 0赞

# 最长回文子序列 #

这是一个典型的DP动态规划解决的问题

# 代码如下 #

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    
    using namespace std;
    
    
    static const string a = "abASDFGGFDSAfgdba";
    static const int lena = a.length();
    
    //递归求解
    int ByRecursion(int i, int j)
    {
        if (i>j)
            return 0;
    
        if (i == j)
            return 1;
    
        if (a[i] == a[j])
            return 2 + ByRecursion(i + 1, j - 1);
        else
        {
            int a = ByRecursion(i + 1, j);
            int b = ByRecursion(i, j - 1);
            return max(a, b);
        }
    }
    
    int ByDPLPS()
    {
        int** cal = new int*[lena];
        int** flag = new int*[lena];
        for (int i = 0; i<lena; i++)
        {
            cal[i] = new int[lena];
            flag[i] = new int[lena];
        }
    
    
        for (int i = 0; i<lena; i++)
        {
            for (int j = 0; j<lena; j++)
            {
                cal[i][j] = (i == j) ? 1 : 0;
                flag[i][j] = 0;
            }
        }
    
        //其实思路和最大公共子序列是一样的,不一样的是下面循环的设计
        //cal[i][j]表示从i到j的子序列是否是回文字符串
        //cal[i][j]=cal[i+1][j-1]+2;  表明i是一来后面的元素i+1,所以i要倒序
        //j是依赖前面的元素,所以要顺序遍历
        for (int i = lena - 1; i >= 0; i--)
        {
            for (int j = i + 1; j<lena; j++)
            {
                if (a[i] == a[j])
                {
                    cal[i][j] = cal[i + 1][j - 1] + 2;
                    flag[i][j] = 0;
                }
                else if (cal[i + 1][j] > cal[i][j - 1])
                {
                    cal[i][j] = cal[i + 1][j];
                    flag[i][j] = 2;
                }
                else
                {
                    cal[i][j] = cal[i][j - 1];
                    flag[i][j] = 3;
                }
    
            }
        }
    
        int maxLen = cal[0][lena - 1];
        char* res = new char[maxLen + 1];
        res[maxLen] = '\0';
        int k = maxLen - 1;
        int h = 0;
        int i = 0, j = lena - 1;
    
        while (h <= k)
        {
            if (flag[i][j] == 0)
            {
                res[h++] = a[i++];
                res[k--] = a[j--];
            }
            else if (flag[i][j] == 2)
                i++;
            else
                j--;
        }
    
        cout << "LPS is following:" << endl << res << endl;
        for (int i = 0; i<lena; i++)
            delete[] cal[i], flag[i];
        delete[] cal, flag, res;
        return maxLen;
    }
    
    
    int main()
    {
        int len = ByRecursion(0, lena - 1);
        cout << "LPS: " << len << endl;
    
        len = ByDPLPS();
        cout << "LPS: " << len << endl;
        system("pause");
    
    }