学步园

今天研究了动态规划算法的基本思想和解题思路，自己测试写下这段代码，以验证vc/dev下编译通过，哈哈。。

#include <stdio.h>
#include <stdlib.h>
#define N 8
#define M 7
char x[N+1]={' ','a','b','c','d','g','f','a','c'};
char y[M+1]={' ','b','d','g','h','a','c','d'};
int z[N+1][M+1];
int h[N+1][M+1];
void Length()
{
    int i,j;
    for(i=0;i<N;i++)
    z[i][0]=0;
    for(j=0;j<M;j++)
    z[0][j]=0;
   
    for(i=1;i<=N;i++)
    for(j=1;j<=M;j++)
    {
        if(x[i]==y[j])
        {
             z[i][j]=z[i-1][j-1]+1;
             h[i][j]=0;
        }
        else if(z[i-1][j]>=z[i][j-1])
        {
            z[i][j]=z[i-1][j];
            h[i][j]=1;
        }
        else
        {
            z[i][j]=z[i][j-1];
            h[i][j]=2;
        }
    }
}

void LCS(int i,int j)
{
    if(i==0||j==0)
    return;
   
    if(h[i][j]==0)
    {
        LCS(i-1,j-1);
        printf("%c ",x[i]);
    }
    else if(h[i][j]==1)
    {
        LCS(i-1,j);   
    }
    else
    {
        LCS(i,j-1);   
    }
   
}

int main()
{
 Length();
    printf("%d\n",z[N][M]);
    LCS(N,M);
 system("pause");
 return 0;
}