> 从上面几个结论看过来,我们就可以知道当xm != yn时
> f(m,n)一定是
> f(m-1,n)+t(xm,_)
> f(m,n-1)+t(xm,_)
  这里可能是个小错误, f(m, n) = f(m, n-1) + t(_,yn)?
> f(m-1,n-1)+t(xm,yn)
> 中的最大的一个.
> 
> ****************************************************************************
> 当xm == yn 时候
> ****************************************************************************
> 这个时候很简单，肯定是
> f(m,n) = f(m-1,n-1) + t(xm,yn);
> 
> 综合上面所有的东西,我们就完成了为动态规划提供子结构的过程(这样说是不是有语
> 
> 病??),剩下就是LCS的编写工作了.
> 
> 不过,有点要提醒一下,就是初始的时候,比如f(m,0)或者f(0,n)它们不是很简单的置成0
> 
> 的,它们其中有一个不是空集
> 而是这样的f(m,0) = f(m-1,0)+t(m,_)     f(0,n) = f(0,n-1)+ t(_,n)
> 只有f(0,0) = 0.就是上下两个都是空集嘛.
> 小弟就是这里WA了.-_-|||
> 
> 怡笑大方...

• 谢谢archerstarlee 的指正 (160) 2004huangyimin 2008-07-29 13:20:13