动态规划解决最长公共序列

#include <iostream>
#include <mem.h>
using namespace std;


//a为一种一个字符串，dir为方向阵，aindex为a的长，bindex为b的长，index用来模仿树的节点
int LCS(char a[],char dir[100][100],int aindex ,int bindex,int index)
{

  if(aindex == 0||bindex == 0)
  {
    return 1 ;
  }
  // cout << aindex<<"       " <<bindex<<endl;
  if(dir[aindex][bindex]=='1')
  {
       LCS(a,dir,aindex-1,bindex-1,index+1);
       cout<<index << "  "<< a[aindex-1] << "   " ;
  }
  else {
    if(dir[aindex][bindex]=='2')
    {
        LCS(a,dir,aindex-1,bindex,index);
    }else if(dir[aindex][bindex]=='3'){
        LCS(a,dir,aindex,bindex-1,index);
    }else if(dir[aindex][bindex]=='4')
    {
         LCS(a,dir,aindex-1,bindex,index+1);
         LCS(a,dir,aindex,bindex-1,index+1);
    }
  }
}

int main()
{
    char  a[] = {'5' , '6' ,'a' , 'b' , 'c' ,'7'};
    char  b[] = {'4','a','6','b','5','a','c','e','7'};
    int lengtha = sizeof(a)/sizeof(a[0]);
    int lengthb = sizeof(b)/sizeof(b[0]);
    int  ab[100][100];
    char dir[100][100];//记录方向
    for (int i = 1 ; i < lengtha; i ++)
            ab[i][0] = 0 ;

    for (int i = 0 ; i < lengthb; i ++)
            ab[0][i] = 0 ;
    for(int i = 1 ; i<=lengtha ; i ++)
    {
        for(int j = 1 ; j <=lengthb ; j ++)
        {
            if(a[i-1] == b[j-1])
            {
                ab[i][j] = ab[i-1][j-1] +1 ;
                dir[i][j] = '1';
            }else if(ab[i-1][j]>ab[i][j-1])
            {
                ab[i][j] = ab[i-1][j];
                 dir[i][j] = '2';

            }else if(ab[i-1][j]<ab[i][j-1]){
                  ab[i][j] = ab[i][j-1];
                  dir[i][j] = '3';
            }
            else {//相等
                 ab[i][j] = ab[i][j-1];
                 dir[i][j] = '4';

            }
        }
    }
    for(int i = 0 ; i <= lengtha;i++)
    {
        for (int j = 0 ; j <= lengthb ; j++)
        {
            cout <<  ab[i][j];
        }
        cout << endl;
    }
    for(int i = 0 ; i <= lengtha;i++)
    {
        for (int j = 0 ; j <= lengthb ; j++)
        {
            cout <<  dir[i][j];
        }
        cout << endl;
    }

    LCS(a,dir,lengtha,lengthb,0);

    return 0;
}

先上代码，我贴出结果图来，结果图是用树来表示的那种（假树），后边懒得处理了。

其中从小到大0  1  2   3  4  5 这样的顺序，把字符串成一串，比如 7  c   b  a ，如果前边有相同的index，比如，那么这俩是可以替换的，模仿二叉树。

其中动态规划的原理：