动态规划算法简介

1 基本概念

维基百科对动态规划（Dynamic programming，DP）的定义：它是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

动态规划是通过组合子问题的解而解决整个问题的，通过将问题分解为相互不独立的子问题（各个子问题包含有公共的子问题，也叫重叠子问题），对每个子问题求解一次，将其结果保存到一张辅助表中，避免每次遇到各个子问题时重新计算。动态规划通常用于解决最优化问题。

2 动态规划应用前提

什么时候可以使用动态规范方法解决问题呢？这个问题需要讨论一下，采用动态规范方法的最优化问题需具备三个要素：最优子结构性质、重叠子问题性质和无后效性。

2.1 最优子结构性质

最优子结构是指问题的一个最优解中包含了其子问题的最优解。在动态规划中，每次采用子问题的最优解来构造问题的一个最优解。寻找最优子结构，遵循的共同的模式：

• 1 问题的一个解可以是做一个选择，得到一个或者多个有待解决的子问题。
• 2 假设对一个给定的问题，已知的是一个可以导致最优解的选择，不必关心如何确定这个选择。
• 3 在已知这个选择后，要确定哪些子问题会随之发生，如何最好地描述所得到的子问题空间。
• 4 利用“剪贴”技术，来证明问题的一个最优解中，使用的子问题的解本身也是最优的。

最优子结构在问题域中以两种方式变化：

• 1 利用“剪贴”技术，来证明问题的一个最优解中，使用的子问题的解本身也是最优的。
• 2 在决定一个最优解中使用哪些子问题时有多少个选择。

动态规划按照自底向上的策略利用最优子结构，即：首先找到子问题的最优解，解决子问题，然后逐步向上找到问题的一个最优解。为了描述子问题空间，可以遵循这样一条有效的经验规则，就是尽量保持这个空间简单，然后在需要时再扩充它。

注意：

在不能应用最优子结构的时候，就一定不能假设它能够应用。 警惕使用动态规划去解决缺乏最优子结构的问题。使用动态规划时，子问题之间必须是相互独立的。可以这样理解，N个子问题域互不相干，属于完全不同的空间。

2.2 重叠子问题性质

用来解决原问题的递归算法可以反复地解同样的子问题，而不是总是产生新的子问题。重叠子问题是指当一个递归算法不断地调用同一个问题。动态规划算法总是充分利用重叠子问题，通过每个子问题只解一次，把解保存在一个需要时就可以查看的表中，每次查表的时间为常数。

由计算出的结果反向构造一个最优解：把动态规划或者是递归过程中作出的每一次选择都保存下来（保存的是每次作出的选择），在最后就可以通过这些保存的选择来反向构造出最优解

做备忘录的递归方法：这种方法是动态规划的一个变形，它本质上与动态规划是一样的，但是比动态规划更好理解！

• 1 使用普通的递归结构，自上而下的解决问题。
• 2 当在递归算法的执行中每一次遇到一个子问题时，就计算它的解并填入一个表中。以后每次遇到该子问题时，只要查看并返回表中先前填入的值即可。

2.3 无后效性

即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。

3 动态规划设计步骤

动态规划问题设计步骤如下：

• 1 描述最优解的结构。
• 2 递归定义最优解的值。
• 3 按自底向上的方式计算最优解的值。
• 4 由计算出的结果构造出一个最优解。

第一步是选择问题的在什么时候会出现最优解，通过分析子问题的最优解而达到整个问题的最优解。在第二步，根据第一步得到的最优解描述，将整个问题分成小问题，直到问题不可再分为止，层层选择最优，构成整个问题的最优解，给出最优解的递归公式。第三步根据第二步给的递归公式，采用自底向上的策略，计算每个问题的最优解，并将结果保存到辅助表中。第四步骤是根据第三步中的最优解，借助保存在表中的值，给出最优解的构造过程。

4 应用举例

0-1背包问题，问题描述：给定n种物品和一背包。物品i的重量是Wi，其价值为Pi，背包的容量为j。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

0-1背包的状态转换方程为： f[i,j] = Max{ f[i-1,j-Wi]+Pi( j >= Wi ), f[i-1,j] }。

其中f[i,j]表示在前i件物品中选择若干件放在承重为 j 的背包中，可以取得的最大价值。Pi表示第i件物品的价值。决策：为了背包中物品总价值最大化，第 i件物品应该放入背包中吗 ？

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

只要能通过找规律手工填写出上面这张表就算理解了0-1背包的动态规划算法。

首先要明确这张表是自底向上，自左向右生成的。

为叙述方便，用e2单元格表示e行2列的单元格，这个单元格的意义是用来表示只有物品e时，有个承重为2的背包，那么这个背包的最大价值是0，因为e物品的重量是4，背包装不下。对于d2单元格，表示只有物品e和d时，承重为2的背包，所能装入的最大价值，仍然是0，因为物品e,d都不能装入背包。同理，c2=0，b2=3,a2=6。

对于承重为8的背包，a8=15,是怎么得出的呢？根据01背包的状态转换方程，需要考察两个值，一个是f[i-1,j],对于这个例子来说就是b8的值9，另一个是f[i-1,j-Wi]+Pi；在这里， f[i-1,j]表示我有一个承重为8的背包，当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值，f[i-1,j-Wi]表示我有一个承重为6的背包（等于当前背包承重减去物品a的重量），当只有物品b,c,d,e四件可选时，这个背包能装入的最大价值，f[i-1,j-Wi]就是指单元格b6,值为9，Pi指的是a物品的价值，即6；由于f[i-1,j-Wi]+Pi = 9 + 6 = 15 大于f[i-1,j] = 9，所以物品a应该放入承重为8的背包；由此得到a8=15。

5 总结

动态规划的核心就是找到问题的最优子结构，在找到最优子结构之后的消除重复子问题。最后采用动态规划的自底向上的递推可以轻松的找出最优解的构造过程。

——————吕占斌，2015.01.30