大家好，又见面了，我是全栈君。
1. 对于序列x[1,i]和y[1,j]，推导递推公式
1.a 假设当前元素同样，那么就将当前最大同样数+1
2.b 假设当前元素不同。那么就把当前最大同样数“传递”下去
1.a 假设当前元素同样，那么就将当前最大同样数+1
2.b 假设当前元素不同。那么就把当前最大同样数“传递”下去
因此递推公式为：
x[i] == y[j] : dp[i][j] = Max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1 x[i] != y[j] : dp[i][j] = Max(dp[i][j-1],dp[i-1][j])
因为x[i]!=y[j]的情况不难能够对x[i]==y[j]时的情况化简得：
x[i] == y[j] : dp[i][j] = dp[i-1][j-1] + 1
2. 依据公式填充dp数组
比如，对于ABCDBC 和 BADC这两个字符串，在最长公共子串时 ：
2.a 第一列置0，即将dp[0][j]和dp[i][0] = 0
2.b 运用公式填表，例如以下所看到的
A B C D B C 0 0 0 0 0 0 B 0 0 1 1 1 2 2 A 0 1 1 1 1 2 2 D 0 1 1 1 2 2 2 C 0 1 1 2 2 2 3
3. C# 代码演示样例：
void Main()
{
var r = DP_LCS("ABCDBC","BADC");
Console.WriteLine(r);
}
static int DP_LCS(string x, string y){
int[,] dpArr = new int[x.Length+1,y.Length+1];
for(var i = 0 ;i <= x.Length; i++){
for(var j = 0 ;j <= y.Length; j++){
if(i == 0 || j == 0){
dpArr[i,j] = 0;
}
else if (x[i - 1] == y[j - 1]){
dpArr[i,j] = dpArr[i-1,j-1] + 1;
}
else {
dpArr[i,j] = Math.Max(dpArr[i-1,j],dpArr[i,j-1]);
}
}
}
return dpArr[x.Length, y.Length];
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116160.html原文链接：https://javaforall.net
