动态规划算法简介

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。