| title | date | tags | author | comments |
|---|---|---|---|---|
算法导论研读与分析（八） |
2013-09-07 03:00:00 -0700 |
最长公共子序列，最优二叉搜索树，动态规划 |
maclaon |
false |
#动态规划经典问题求解
题目：如果字符串$$B$$的所有字符按其在字符串中的顺序出现在另外一个字符串$$A$$中，则字符串$$B$$称之为字符串$$A$$的子串。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
$$C\left[ {i,j} \right] = \left{ {\matrix{ 0 \cr {C\left[ {i - 1,j - 1} \right] + 1} \cr {\max \left{ {C\left[ {i,j - 1} \right],C\left[ {i - 1,j} \right]} \right}} \cr
} \matrix{ {if{\rm{ }}i = 0{\rm{ }}or{\rm{ }}j = 0} \cr {if{\rm{ }}i,j > 0,{x_i} = {y_j}} \cr {if{\rm{ }}i,j > 0,{x_i} \ne {y_j}} \cr
} } \right.$$
上述求解最长公共子序列的多项式解说如下:
- 递归终止条件，当前状态下的子序列的索引为$$0$$时，最长公共子序列的长度为$$0$$
- 当前状态下的字符与已经成最长公共子序列中的字符相等的话，那么该最长公共子序列的长度加一。
- 当前状态下的字符与已经成最长公共子序列中的字符不相等的话，那么取当前最长公共子序列加入该字符后的公共最长子序列。
是一个很典型的动态规划的问题，那么这里的状态转移方程式最长相等的公共子序列，那么也可以是最长递增、递增子序列这些问题都是该问题的变种，但是解决思路上是一致的。
最长连续相同子序列的问题主要是应用再$$DNA$$基因序列检测的过程中。
利用最优二叉搜索树来实现树的搜索代价最小。树上的每一个节点都有一个被搜索到的概率值$$p_i$$，搜索一个节点的花费为$$p_i*(depth(k_i)+1)$$，如何构造一个二叉查找树使搜索树上的所有节点的花费最小即为实现最优二叉查找树的问题。该问题可以用动态规划的思路实现。
现实生活中，查找的关键字是有一定的概率的，就是说有的关键字可能经常被搜索，而有的很少被搜索，而且搜索的关键字可能不存在，为此需要根据关键字出现的概率构建一个二叉树。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频——所谓动态调频、高频先现原则，以减少用户翻查次数，使得经常用的词汇被放置在前面，这样就能有效地加快查找速度，比如搜狗输入法，或者是单词翻译查询，翻译一篇文章中的英文对法文的翻译中，可能会根据英文这个词的使用频率来尽快的找到法语对应的解释，提高翻译速度