动态规划:最长公共子序列和最长公共子串

递推方程:

     0,  i = 0 or j = 0

C[i,j] =   C[i-1,j-1] + 1, i,j > 0 and Xi = Yj

     max{C[i-1,j],C[i,j-1]}, i,j > 0 and Xi != Yj

 使用二维int[][]辅助存储过程

Xn串和Ym串,从后往前看,如果Xn=Ym,则最长公共子序列为Xn-1和Ym-1串的最长公共子序列加1

            如果Xn != Ym,则最长公共子序列必在Xn-1和Ym与Xn与Ym-1中产生

最长公共子串和最长公共子序列类似,只是在Xi != Yj时,把C[i][j]置0,一路注意保存最大值

原文地址:https://www.cnblogs.com/zawjdbb/p/7351215.html