计算最优值-数据分析方法梅长林
2.3、计算最优值直接利用上节节末的递归式，我们将很容易就能写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=
-
Procedure LCS_LENGTH(X,Y);
-
begin
-
m:=length[X];
-
n:=length[Y];
-
for i:=1 to m do c[i,0]:=0;
-
for j:=1 to n do c[0,j]:=0;
-
for i:=1 to m do
-
for j:=1 to n do
-
if x[i]=y[j] then
-
begin
-
c[i,j]:=c[i-1,j-1]+1;
-
b[i,j]:="↖";
-
end
-
else if c[i-1,j]≥c[i,j-1] then
-
begin
-
c[i,j]:=c[i-1,j];
-
b[i,j]:="↑";
-
end
-
else
-
begin
-
c[i,j]:=c[i,j-1];
-
b[i,j]:="←"
-
end;
-
return(c,b);
-
end;
由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=
想深入了解如何用动态规划算法解决最长公共子序列问题吗？你可以查看以下链接获取更多详情：
这些资源不仅能让你更全面地理解算法原理，还能帮助你更有效地应用于实际问题！
