二、序列相似性定义

动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。而分治法中的各个子问题是独立的（即不包含公共的子问题），因此一旦递归地求出各子问题的解后，便可自上而下地将子问题的解合并成问题的解。在求解过程中该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的，动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果能够保存已经解决的子问题的答案，那么在需要的时候直接找出已求得的答案。最优的整体配准(o ......