动态规划

动态规划（Dynamic Programming）是解决多阶段决策问题常用的最优化理论，动态规划和分治法一样，也是通过定义子问题，先求解子问题，然后在由子问题的解组合出原问题的解。但是它们之间的不同点是分治法的子问题之间是相互独立的，而动态规划的子问题之间存在堆叠关系（递推关系式确定的递推关系）。动态规划方法的原理就是把多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。动态规划问题有很多模型，常见的有线性模型、（字符或数字）串模型、区间模型、状态压缩模型，等等，本节课后面介绍的最长公共子序列问题，就是一个典型的串模型。

动态规划适合求解多阶段（状态转换）决策问题的最优解，也可用于含有线性或非线性递推关系的最优解问题，但是这些问题都必须满足最优化原理和子问题的“无后向性”。

最优化原理：

最优化原理其实就是问题的最优子结构的性质，如果一个问题的最优子结构是不论过去状态和决策如何，对前面的决策所形成的状态而言，其后的决策必须构成最优策略。也就是说，不管之前的决策是否是最优决策，都必须保证从现在开始的决策是在之前决策基础上的最优决策，则这样的最优子结构就符合最优化原理。

无后向性（无后效性）：

所谓“无后向性”，就是当各个阶段的子问题确定以后，对于某个特定阶段的子问题来说，它之前各个阶段的子问题的决策只影响该阶段的决策，对该阶段之后的决策不产生影响.对于某一个状态 S 来说，只要 S 状态确定了以后，S 以后的那些依靠 S 状态做最优选择的状态也就都确定了，S 之后的状态只受 S 状态的影响。也就是说，无论之前是经过何种决策途径来到了 S 状态，S 状态确定以后，其后续状态的演化结果都是一样的，不会因为到达 S 状态的决策路径的不同而产生不同的结果，这就是无后向性。

动态规划的基本思想

和分治法一样，动态规划解决复杂问题的思路也是先对问题进行分解，然后通过求解小规模的子问题再反推出原问题的结果。但是动态规划分解子问题不是简单地按照“大事化小”的方式进行的，而是沿着决策的阶段来划分子问题，决策的阶段可以随时间划分，也可以随着问题的演化状态来划分。分治法要求子问题是互相独立的，以便分别求解并最终合并出原始问题的解。分治法对所有的子问题都“一视同仁”地进行计算求解，如果分解的子问题中存在相同子问题，就会存在重复求解子问题的情况。

比如某个问题 A，第一次分解为 A1 和 A2 两个子问题，A1 又可分解为 A11 和 A12 两个子问题，A2 又分解为 A21 和 A22 两个子问题，分治法会分别求解 A11、A12、A21 和 A22 四个子问题，即便 A12 和 A21 是相同的子问题，分治法也依然会计算四次子问题的解，这就存在重复计算的问题，重复计算相同的子问题会影响求解的效率。

与之相反，动态规划法的子问题不是互相独立的，子问题之间通常有包含关系，甚至两个子问题可以包含相同的子子问题。比如，子问题 A 的解可能由子问题 C 的解递推得到，同时，子问题 B 的解也可能由子问题 C 的解递推得到。对于这种情况，动态规划法对子问题 C 只求解一次，然后将其结果保存在一张表中（此表也被称为备忘录）。当求解子问题 A 或子问题 B 的时候，如果发现子问题 C 已经求解过（在备忘录表中能查到），则不再求解子问题 C，而是直接使用从表中查到的子问题 C 的解，避免了子问题 C 被重复计算求解的问题。

动态规划法不像贪婪法或分治法那样有固定的算法实现模式，线性规划问题和区间动态规划问题的实现方法就完全不同。作为解决多阶段决策最优化问题的一种思想，可以用带备忘录的穷举方法实现，也可以根据堆叠子问题之间的递推公式用递推的方法实现。但是从算法设计的角度分析，使用动态规划法一般需要四个步骤，分别是：

1. 定义最优子问题（最优解的子结构）
2. 定义状态（最优解的值）
3. 定义决策和状态转换方程（定义计算最优解的值的方法）
4. 确定边界条件

这四个问题解决了，算法也就确定了。接下来就结合两个实例分别介绍这四个步骤，这两个例子分别是经典的 0-1 背包问题和最长公共子序列问题。

定义最优子问题

定义最优子问题，也就是最优解的子结构，它确定问题的优化目标以及如何决策最优解，并对决策过程划分阶段。所谓阶段，可以理解为一个问题从开始到解决需要经过的环节，这些环节前后关联。

对于 0-1 背包问题，每选择装一个物品可以看做是一个阶段，其子问题就可以定义为每次向包中装（选择）一个物品，直到超过背包的最大容量为止。
最长公共子序列问题可以按照问题的演化状态划分阶段，这就需要先定义状态，有了状态的定义，只要状态发生了变化，就可以认为是一个阶段。

定义状态

状态既是决策的对象，也是决策的结果，对于每个阶段来说，对起始状态施加决策，使得状态发生改变，得到决策的结果状态。初始状态经过每一个阶段的决策（状态改变）之后，最终得到的状态就是问题的解。当然，不是所有的决策序列施加于初始状态后都可以得到最优解，只有一个决策序列能得到最优解。状态的定义是建立在子问题定义基础之上的，因此状态必须满足无后向性要求。必要时，可以增加状态的维度，引入更多的约束条件，使得状态定义满足无后向性要求。

0-1 背包问题本身是个线性过程，但是如果简单将状态定义为装入的物品编号，也就是定义 s[i] 为装入第 i 件物品后获得的最大价值，则子问题无法满足无后向性要求，原因是之前的任何一个决策都会影响到所有的后序决策（因为装入物品后背包容量发生变化了），因此需要增加一个维度的约束。

考虑到每装入一个物品，背包的剩余容量就会减少，故而选择将背包容量也包含在状态定义中。最终背包问题的状态 s[i,j] 定义为将第 i 件物品装入容量为 j 的背包中所能获得的最大价值。对于最长公共子序列问题，如果定义 str1[1…i] 为第一个字符串前 i 个字符组成的子串，定义 >str2[1…j] 为第二个字符串的前 j 个字符组成的子串，则最长公共子序列问题的状态 s[i,j] 定义为 str1[1…i] 与 str2[1…j] 的最长公共子序列长度。

定义决策和状态转换方程

决策就是能使状态发生转变的选择动作，如果选择动作有多个，则决策就是取其中能使得阶段结果最优的那一个。状态转换方程是描述状态转换关系的一系列等式，也就是从 n-1 阶段到 n 阶段演化的规律。状态转换取决于子问题的堆叠方式，如果状态定义得不合适，会导致子问题之间没有重叠，也就不存在状态转换关系了。没有状态转换关系，动态规划也就没有意义了，实际算法就退化为像分治法那样的朴素递归搜索算法了。

0-1 背包问题的决策很简单，那就是决定是否选择第 i 件物品，即判断装入第 i 件物品获得的收益最大还是不装入第 i 件物品获得的收益最大。如果不装入第 i 件物品，则背包内物品的价值仍然是 s[i-1,j] 状态，如果装入第 i 件物品，则背包内物品的价值就变成了 s[i,j-Vi] + Pi 状态，其中 Vi 和 Pi 分别是第 i 件物品的容积和价值，决策的状态转换方程就是：

                                  s[i,j]=max(s[i−1,j],s[i,j−Vi]+Pi)

最长公共子序列问题的决策方式就是判断 str1[i] 和 str2[j] 的关系，如果 str1[i] 与 str2[j] 相同，则公共子序列的长度应该是 s[i-1,j-1] + 1， 否则就分别尝试匹配 str1[1…i+1] 与 str2[1…j] 的最长公共子序列，以及 str1[1…i] 与 str2[1…j+1] 的最长公共子序列，然后取二者中较大的那个值作为 s[i,j] 的值。最长公共子序列问题的状态转换方程就是：

                                          s[i,j]=s[i−1,j−1]+1

其中， str1[i] 与 str2[j] 相同。

                                    s[i,j]=max(s[i,j−1],s[i−1,j])

其中， str1[i] 与 str2[j] 不相同。

确定边界条件

对于递归加备忘录方式（记忆搜索）实现的动态规划方法，边界条件实际上就是递归终结条件，无需额外的计算。对于使用递推关系直接实现的动态规划方法，需要确定状态转换方程的递推式的初始条件或边界条件，否则无法开始递推计算。

0-1 背包问题的边界条件很简单，就是没有装入任何物品的状态：

                                            s[0,Vmax]=0

若要确定最长公共子序列问题的边界条件，要从其决策方式入手，当两个字符串中的一个长度为 0 时，其公共子序列长度肯定是 0，因此其边界条件就是：

                                      s[i,j]=0

其中，i=0 或 j=0。

最长公共子序列（LCS）问题

这一课我们用一个经典的最长公共子序列问题为例，来说明一下如何将上面的原理分析应用到算法实现过程中。最长公共子序列（LCS，Longest Common Subsequence）的定义是：一个序列 S，如果分别是两个或多个已知序列的子序列，且是符合此条件的子序列中最长的，则称 S 为已知序列的最长公共子序列。

关于子序列的定义通常有两种方式，一种是对子序列没有连续的要求，其子序列的定义就是原序列中删除若干元素后得到的序列；另一种是对子序列有连续的要求，其子序列的定义是原序列中连续出现的若干个元素组成的序列。

求解子序列是非连续的最长公共子序列问题，也是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。下面将介绍对子序列没有连续性要求的情况下应如何用动态规划法来解决最长公共子序列问题。

根据前面的分析，假如有两个字符串 str1[1..m] 和 str2[1..n] ，其最长公共子序列问题在某一个决策阶段的状态 s[i,j] 定义为 str1[1…i] 与 str2[1…j] 的最长公共子序列长度（i<=m, j<=n），这个状态 s[i,j] 其实也就是子问题的定义，可以将其描述为：求字符串 str1<1..m> 中从第 1 个到第 i（i <= m） 个字符组成的子串 str1<1…i> 和字符串 str2<1..n> 中从第 1 个到第 j(j <= n) 个字符组成的子串 str2<1…j> 的最长公共序列。

接下来要找出子问题的最优序列中状态 s[i,j] 的递推关系。分析 s[i,j] 的递推关系要从 str1[i] 和 str2[j] 的关系入手，根据非连续最长公共子序列问题的定义，如果 str1[i] 和 str2[j] 相同，则 s[i,j] 就是 s[i-1,j-1] 的最长公共序列 ＋1，如果 str1[i] 和 str2[j] 不相同，则 s[i,j] 就是 s[i-1,j] 的最长公共序列和 s[i,j-1] 的最长公共序列中较大的那一个。

最后是确定状态转移递推关系的边界值。很显然，当 str1 和 str2 中任何一个的长度为 0，则其最长公共子序列即为 0，当状态递推到 s[m,n] 时， s[m,n] 就是原始问题的最长公共子序列长度。完整的状态转移递推关系如下：

DpLcs() 函数是用动态规划法解决最长公共子序列问题的算法实现，从下面的代码中可以看出，两个 for 循环实际上是做了个广域搜索，将所有子序列的结果都求出来了，只有 s[m,n] 代表的是原始问题的最长公共子序列长度。

int DpLcs(const std::string& str1, const std::string& str2, int s[MAX_STRING_LEN][MAX_STRING_LEN])
{
    std::string::size_type i,j;

    for(i = 1; i <= str1.length(); i++)
        s[i][0] = 0;
    for(j = 1; j <= str2.length(); j++)
        s[0][j] = 0;

    for(i = 1; i <= str1.length(); i++)
    {
        for(j = 1; j <= str2.length(); j++)
        {
            if((str1[i - 1] == str2[j - 1]))
            {
                s[i][j] = s[i - 1][j - 1] + 1; 
            }
            else
            {
                s[i][j] = std::max(s[i - 1][j], s[i][j - 1]); 
            }
        }
    }

    return s[str1.length()][str2.length()];
}