什么是动态规划

定义

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

过程

每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

基本思想与策略

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。故大部分的动态规划都是在做一个填表的过程，故有时候动态规划也称为填表法。
与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。

一些术语

状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。
无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多问题中，决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。
策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。最优性原理实际上是要求问题的最优策略的子策略也是最优。

动态规划使用条件

采用动态规划求解的问题一般要具有3个性质：

• 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构。即满足最优化原理。最优子结构也就是要求我的子问题也是最优的。这个地方一定要结合无后效性考虑（参见零钱兑换问题中的错误贪心法）。
• 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响当前的状态，只与当前状态有关。

• 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

  求解动态规划问题的一般思路

• 将原问题分解为子问题 (注意:1,子问题与原问题形式相同或类似,只是问题规模变小了,从而变简单了; 2,子问题一旦求出就要保存下来,保证每个子问题只求解一遍)

• 确定状态(状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个”状态”,一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为”状态空间”.状态就是某个问题某组变量,状态空间就是该问题的所有组变量) 另外:整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间
• 确定一些初始状态(边界条件)的值 (视情况而定,真正实践动规千变万化)
• 确定状态转移方程 (这一步和第三步是最关键的 记住”人人为我”递推,由已知推未知)

另一个版本:

• 找到状态和选择
• 明确dp数组/函数的定义

• 寻找状态之间的关系

  动态规划三部曲

• 建立状态转移方程
  这一步是最难的，大部分人都被卡在这里。这一步没太多的规律可说，只需抓住一个思维：当做已经知道~的值，然后想办法利用它们求得。在“斐波那契数列”的例子中，状态转移方程即为斐波那契递推式。

• 缓存并复用以往结果
  这一步不难，但是很重要。如果没有合适地处理，很有可能就是指数和线性时间复杂度的区别。假设在“斐波那契数列”的例子中，我们不能用显式方程，只能用状态转移方程来解，那就试试递归算法了。但是如果刚刚缓存过，只需复用这个子结果，那么将只需一次加法运算即可。
• 按顺序从小往大算
  这里的“小”和“大”对应的是问题的规模，在这里也就是我们要从 , , … 到 依次顺序计算。当问题复杂起来的时候，必须记住这也是目标之一。也就是从整个状态的初始态向终止态运行。

  递归到动态规划

  暴力递归—->带备忘录的递归—->迭代的动态规划解法

动态规划的算法实现

动态规划的主要难点在于理论上的设计，也就是上面4个步骤的确定，一旦设计完成，实现部分就会非常简单。
使用动态规划求解问题，最重要的就是确定动态规划三要素：
（1）问题的阶段
（2）每个阶段的状态
（3）从前一个阶段转化到后一个阶段之间的递推关系。
递推关系必须是从次小的问题开始到较大的问题之间的转化，从这个角度来说，动态规划往往可以用递归程序来实现，不过因为递推可以充分利用前面保存的子问题的解来减少重复计算，所以对于大规模问题来说，有递归不可比拟的优势，这也是动态规划算法的核心之处。
确定了动态规划的这三要素，整个求解过程就可以用一个最优决策表来描述，最优决策表是一个二维表，其中行表示决策的阶段，列表示问题状态，表格需要填写的数据一般对应此问题的在某个阶段某个状态下的最优值（如最短路径，最长公共子序列，最大价值等），填表的过程就是根据递推关系，从1行1列开始，以行或者列优先的顺序，依次填写表格，最后根据整个表格的数据通过简单的取舍或者运算求得问题的最优解。

动态规划的局限性

动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是“维数障碍”。

总结

上面罗列了一堆有关动态规划的定义，比较抽象没有基础的人可能看完之后脑海中浮现出一堆问号。那究竟什么是动态规划？别慌，正是由于没有一个统一解，所以只能用形象化的语言去描述它，而不能使用形式化的公式去定义。后面将结合例子，以及算法题来进一步剖析。