最长公共子序列（动态规划）

本是古典何须时尚 2022-08-18 02:19 230阅读 0赞

【题⺫】  
给定两个字符串  str1 和  str2，返回两个字符串的最长公共子序列。  
【举例】  
str1 =“1 A2 C 3 D 4 B5 6 ”， str2 =“B1 D 2 3 C A4 5 B6 A”。  
“123456”或者“12C4B6”都是最长公共子序列，返回哪一个都⾏。  
  
代码实现：

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    
    using namespace std;
    
    #define MAX_COLS 100  //字符串的最大长度
    
    /* dp[i][j]代表str1[0..i]和str2[0..j]之间的最长字串 */
    void getdp(const char* str1, const char* str2,int dp[][MAX_COLS])
    {
        if (str1 == NULL || str2 == NULL)
        {
            return;
        }
    
        int i = 0, j = 0;
        int rows = strlen(str1);  //行数
        int cols = strlen(str2);  //列数
    
        dp[0][0] = ((str1[0] == str2[0]) ? 1 : 0);
    
        /* 求出第一列的dp值 */
        for(i = 1; i < rows; i++)
        {
           dp[i][0] = max(dp[i-1][0],(str1[i] == str2[0] ? 1 : 0)) ;
        }
    
        /* 求出第一行dp值 */
        for(j = 1; j < cols; j++)
        {
            dp[0][j] = max(dp[0][j-1], (str1[0] == str2[j] ? 1 : 0));
        }
    
        for(i = 1; i < rows; i++)
        {
            for(j = 1; j < cols; j ++)
            {
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                if (str1[i] == str2[j])
                {
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
                }
            }
        }
    }
    
    /* 根据str1、str2和dp数组求出最长的公共子序列,并返回 */
    char* getSubList(const char* str1, const char* str2)
    {
        int dp[MAX_COLS][MAX_COLS] = {0};
        char* pres =  NULL;
        int index = 0;
        int i = strlen(str1) - 1;
        int j = strlen(str2) - 1;
    
        /* 求出dp数组 */
        getdp(str1,str2,dp);
        pres = new char[dp[i][j]+1];
        pres[dp[i][j]] = '\0';
        index = dp[i][j] - 1;
    
        while(index >= 0)
        {
            if (j > 0 && dp[i][j] == dp[i][j-1])
            {
               j--;
            }
            else if (i > 0 && dp[i][j] == dp[i-1][j])
            {
                i--;
            }
            else
            {
                pres[index--] = str1[i];
                i--;
                j--;
            }
        }
    
        return pres;
    }
    int main()
    {
        char str1[] = "1A2C3D4B56";
        char str2[] = "B1D23CA45B6A";
    
        cout << getSubList(str1,str2) << endl;
    }