最大公共子序列是动态规划中非常经典的例子，其规则是找出两个数组序列中顺序相同但不一定连续、最长的公共子序列
我们用JavaScript来实现它：
<script type="text/javascript"> var c=new Array(20),b=new Array(20); for (var i=0,len=c.length>b.length?c.length:b.length;i<len;i++) { c[i]=new Array(20); b[i]=new Array(20); } function LCSLength(m,n,x,y){ for(var i=1;i<=m;i++)c[i][0]=0; for(var j=0;j<=n;j++)c[0][j]=0; for(i=1;i<=m;i++){ for (j=1;j<=n;j++) { if (x[i-1]==y[j-1]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1; } else if(c[i-1][j]>=c[i][j-1]){ c[i][j]=c[i-1][j]; b[i][j]=2; }else{ c[i][j]=c[i][j-1]; b[i][j]=3; } } } } function LCS(m,n){ if (m==0 || n==0) { return; } if (b[m][n]==1) { LCS(m-1,n-1); console.log(X[m-1]+" "+m); } else if(b[m][n]==2){ LCS(m-1,n); }else{ LCS(m,n-1); } } var X=["A","B","C","B","D","A","B"]; var Y=["B","D","C","A","B","A"]; LCSLength(X.length,Y.length,X,Y); //alert(c[X.length][Y.length]); LCS(X.length,Y.length); //alert(b); </script>输出为：B 2 C 3 B 4 A 6