LCS笔记

状态的表示：f[i][j]表示第一个字符串的前i个字符，与第二个字符串的前j个字符，能形成的最长公共子序列的长度 边界条件：f[0][i]=f[i][0]=0 因为一个空字符串和另一个长度为i的字符串能形成的最长公共子序列长度为0 这样的话，答案的表示就是f[s1.size()][s2.size()] A[i]==B[j]时，说明A[i]与B[j]正好是相等的，这可以让最长公共子序列的长度增加1，接下来可以转化到A的前i-1个字符与B的前j-1个字符能形成的最长公共子序列的长度这个子问题，所以f[i][j]=f[i-1][j-1]+1 所有动态规划的题目都需要把四个要素考虑清楚： 1状态的表示 2状态转移方程 3边界条件 4答案的表示