[动态规划-二] 最长公共子序列-Longest Common Subsequence

[动态规划-2] 最长公共子序列-Longest Common Subsequence

问题描述：给定两个字符串，求两个数组的最长公共自序列，LCS。

如“ABCDGH” 和 “AEDFHR”的最长公共子序列是 “ADH” ，长度为3;

 “AGGTAB” 和 “GXTXAYB”的最长公共子序列是 “GTAB” ,长度为4.

问题分析：

假设两个字符串分别为A[m],B[n],则我们用L[i,j]来表示子序列A[0]--A[i]和子序列B[0]--B[j]的最长公共子序列的长度。

则：

L[i,j] = L[i-1,j-1] + 1,当A[i] = A[j]时；

L[i,j] = Max{ L[i-1,j], L[i,j-1] },当A[i] \= A[j]时；

画图分析：

代码：

#include<stdio.h>#include<stdlib.h>  int max(int a, int b);  /* 返回最长公共子序列长度 */int lcs( char *X, char *Y, int m, int n ){   int L[m+1][n+1];   int i, j;     /* 自下向上建立L[i,j]数组 */   for (i=0; i<=m; i++)   {     for (j=0; j<=n; j++)     {       if (i == 0 || j == 0)         L[i][j] = 0;//边界条件初始化,由于第0个已经用于边界初始化了，     //所以L[i][j]的表示的是A[0--i-1],B[0--j-1]的LCS了         else if (X[i-1] == Y[j-1])         L[i][j] = L[i-1][j-1] + 1;         else         L[i][j] = max(L[i-1][j], L[i][j-1]);     }   }      return L[m][n];}  int max(int a, int b){    return (a > b)? a : b;}