简单帅哥

文章
7
资源
0
加入时间
2年10月24天

LCS学习笔记

A[i]==B[j]时,说明A[i]与B[j]正好是相等的,这可以让最长公共子序列的长度增加1,接下来可以转化到A的前i-1个字符与B的前j-1个字符能形成的最长公共子序列的长度这个子问题,所以f[i][j]=f[i-1][j-1]+1。状态的表示:f[i][j]表示第一个字符串的前i个字符,与第二个字符串的前j个字符,能形成的最长公共子序列的长度。这样的话,答案的表示就是f[s1.size()][s2.size()]边界条件:f[0][i]=f[i][0]=0。