算法设计-动态规划——最长公共子序列

算法介绍

动态规划：

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的（自底向上求解，底层的解可作为上层解的基础 ）。

问题实例

问题描述：

题目：
给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。
比如字符串1：BDCABA；字符串2：ABCBDAB
则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA

问题分析

对于动态规划的问题我们一般使用数组记录小的分组得到的结果。在该题中我们利用循环比较两条序列的每个字符，分三种情况。
举个小例子：
（S1={1,3,4,5,6,7,7,8}和S2={3,5,7,4,8,6,7,8,2}）

假如S1的最后一个元素 与 S2的最后一个元素相等，那么S1和S2的LCS就等于 {S1减去最后一个元素} 与 {S2减去最后一个元素} 的 LCS 再加上 S1和S2相等的最后一个元素。

假如S1的最后一个元素 与 S2的最后一个元素不等（本例子就是属于这种情况），那么S1和S2的LCS就等于 ： {S1减去最后一个元素} 与 S2 的LCS， {S2减去最后一个元素} 与 S1 的LCS 中的最大的那个序列。

数学公式如下：

伪代码：

①设数组c[][] 和数组b[][]，c[][] 记录此时最长公共子序列的长度，b[][] 记录产生最长公共子序列的过程。
②利用循环遍历比较每个字符，当字符相同时，此时最长公共子序列加一，记录过程为1；当c [i-1] [j] >= c [i] [j-1] 时，c [i] [j] = c [i-1] [j] ，记录过程为2；当c [i-1] [j] < c [i] [j-1] 时，相反，记录为3。
③通过b [i] [j] 倒推出S1和S2的LCS，并记录下标。
④打印输出，结束。

代码：

#include <iostream>
#include <string>

using namespace std;
void LCS(string s1,string s2)
{
    int m=s1.length()+1;
    int n=s2.length()+1;
    int **c;
    int **b;
    c=new int* [m];
    b=new int* [m];
    for(int i=0;i<m;i++)
    {
        c[i]=new int [n];
        b[i]=new int [n];
        for(int j=0;j<n;j++)
            b[i][j]=0;
    }
    for(int i=0;i<m;i++)
        c[i][0]=0;
    for(int i=0;i<n;i++)
        c[0][i]=0;
    for(int i=0;i<m-1;i++)
    {
        for(int j=0;j<n-1;j++)
        {
            if(s1[i]==s2[j])
            {
                c[i+1][j+1]=c[i][j]+1;
                b[i+1][j+1]=1;          //1表示箭头为  左上
            }
            else if(c[i][j+1]>=c[i+1][j])
            {
                c[i+1][j+1]=c[i][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表示箭头向  左
            }
        }
    }
    for(int i=0;i<m;i++)                //输出c数组
    {
        for(int j=0;j<n;j++)
        {
            cout<<c[i][j]<<' ';
        }
        cout<<endl;
    }

    cout<<endl;

    for(int i=0;i<m;i++)                //输出b数组
    {
        for(int j=0;j<n;j++)
        {
            cout<<b[i][j]<<' ';
        }
        cout<<endl;
    }

    char A[20];
    int num=0;
    int x=m-1,y=n-1;
    while(x>=0&&y>=0&&b[x][y]!=0)
    {

        if(b[x][y]==1)
            {
                x--;
                y--;
                A[num]=s1[x];
                num++;
            }
        else if(b[x][y]==2)
            {
                x--;
            }
        else if(b[x][y]==3)
            {
                y--;
            }
    }
    cout<<endl<<"最长公共子序列为：";
    for(int i=num-1;i>=0;i--)
    {
        cout<<A[i];
    }
    cout<<endl<<"长度为："<<c[m-1][n-1]<<endl;
//    stack<char> same;                   //存LCS字符
//    stack<int> same1,same2;             //存LCS字符在字符串1和字符串2中对应的下标，方便显示出来
//    for(int i = m-1,j = n-1;i >= 0 && j >= 0; )
//    {
//        if(b[i][j] == 1)
//        {
//            i--;
//            j--;
//            same.push(s1[i]);
//            same1.push(i);
//            same2.push(j);
//        }
//        else if(b[i][j] == 2)
//                i--;
//        else
//                j--;
//    }
//
//    cout<<endl<<"最长公共子序列为：";
//    while(!same.empty())
//    {
//        cout<<same.top();
//        same.pop();
//    }
//    cout<<endl<<"长度为："<<c[m-1][n-1]<<endl;
}
int main()
{
    string s1="BDCABA";
    string s2="ABCBDAB";
    LCS(s1,s2);
    return 0;
}

结果：

解决本题的关键是如何利用b [i] [j] 逆序找到相应的字符。在本题中，如果b [i] [j] 为1，记录该字符下标，如果b [i] [j] 为2，向上平移1行，如果b [i] [j] 为3，向左平移一行，直到达到边界（b [i] [j] 为0时）。

记录整理一些学习中的问题，如果有不恰当和错误的地方，欢迎批评指正~