(以下简称DP)


基本思想

将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。适合用DP求解的问题,经分解得到的子问题一般不是相互独立的,如果使用分治法求解,有些子问题会被重复计算多次,可以用一个表来记录所有已解决的子问题的答案,不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。

DP算法适用于解最优化问题。通常可以按以下步骤设计:

  1. 找出最优解的性质,并刻画其结构特征;
  2. 递归地定义最优值;
  3. 以自底向上的方式计算出最优值;
  4. 根据计算最优值时得到的信息,构造最优解

基本要素

  1. 最优子结构
    问题的最优解包含了其子问题的最优解。

  2. 重叠子问题
    在用递归算法自顶向下求解问题时,每次产生的子问题并不总是新问题,有些子问题被计算多次。DP算法正式利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,当再次需要解此问题时,只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长,因此用DP算法通常只需要多项式时间,从而获得较高的解题效率。

最长公共子序列

问题描述

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切的说,若给定序列X = {x1, x2, ..., xm},则另一序列Z = {z1, z2, ..., zk},X的子序列是指存在一个严格递增下标序列{i1, i2, ..., ik}使得对于所有j = 1, 2, ..., kzj = xij。例如,序列Z = {B, C, D, B}是序列X = {A, B, C, B, D, A, B}的子序列,相应的递增下标序列为{2, 3, 5, 7}
给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。
例如,若X = {A, B, C, B, D, A, B}Y = {B, D, C, A, B, A},序列{B, C, A}是X和Y的一个公共子序列,但它不是X和Y的最长公共子序列。序列{B, C, B, A}也是X和Y的一个公共子序列,它的长度为4,而且它是X和Y的最长公共子序列,因为X和Y没有长度大于4的公共子序列。

最长公共子序列问题

给定两个序列X = {x1, x2, ..., xm}Y = {y1, y2, ..., ym},找出X和Y的最长公共子序列。

按照DP算法设计的各个步骤求解

  1. 最长公共子序列结构
    设序列X = {x1, x2, ..., xm}Y = {y1, y2, ..., yn}的最长公共子序列为Z = {z1, z2, ..., zk},则

    1. xm = yn,则zk = xm = yn,且Z
  2. 子问题的递归结构

  3. 计算最优值
  4. 构造最长公共子序列
  5. 算法的改进