存档

文章标签 ‘动态规划’

最长公共子序列LCS-算法回顾

2013年4月29日 没有评论 1381次阅读    

最长公共子序列(lcs) 有些变种,比如最长递增子序列,求最小编辑距离;
类似vimdiff等也用的lcs基本原理,猜测可能是这样的:先按行求LCS,或者说编辑距离,然后对需要“编辑”的地方按行求编辑距离。

阅读全文…

Share

最优二叉搜索树-算法回顾

2013年4月29日 没有评论 1375次阅读    

在review之前的书籍,所以把学到的顺手记录在这里了。

由最 优二叉搜索树可以延伸到3X,4X,nX搜素树,只不过在寻找最优子树的时候需要处理3,4的情况。

如果所有节点的概率都想等的话,直接构造完全二叉树就行了。
阅读全文…

Share