动态规划

• 动态规划(Dynamic Programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。
• 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
• 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。
• 动态规划程序设计是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不象前面所述的那些搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划，可以解决各类最优化问题。因此在学习时，除了要对基本概念和方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。

---

思想

动态规划通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以记录所有已解的子问题的答案,不管该子问题以后是否被用到，只要它被计算过，就将其结果记录下，这就是动态规划法的基本思路。具体的动态规划多种多样，但它们具有相同的思想：不做做过的事情。

特征

动态规划的有效性依赖于问题本身所具有的两个重要性质：子问题重叠性质和最优子结构性质。即：

• 在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
• 当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。

于是产生了使用动态规划的动机：

• 避免重叠子问题，将计算过的子问题答案记录下来。
• 利用最优子结构，把问题看作多阶段决策问题，将一个大问题分阶段化成多个小问题。

设计步骤

1. 分析问题结构，建立基本模型；
2. 写出动态规划方程；
3. 以自底向上的方式计算出最优值；
4. 根据计算最优值时得到的信息，构造一个最优解。

注：步骤1-3是动态规划的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。

而在设计动态规划时，须注意方案必须满足如下条件：

• 状态必须满足最优化原理；
• 状态必须满足无后效性。

即是：

• 无论过去的状态和决策如何，对前面的决策所形成的当前状态而言，余下的诸决策必须构成最优策略。可以通俗地理解为子问题的局部最优将导致整个问题的全局最优。
• 某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。 　　

常见状态转移方程

动态规划博大精深，方程千变万化，但对于一些典型问题，还是可以总结出一些简单规律。这里将介绍一些常用的状态转移方程，旨在帮助大家熟悉怎样设计出一个动态规划方案。通过这些简单的模型，大家可以感受对问题状态的划分和状态的转移。

常用优化方法

汪一宁《1D/1D动态规划优化初步》http://wenku.baidu.com/view/681d161ca300a6c30c229f70.html 包含四边形不等式，单调性优化，斜率优化

周源的这篇论文中的例二也包含来了一个斜率优化的方法。挺常见的。 http://wenku.baidu.com/view/df9e2e0d6c85ec3a87c2c5b5.html

当你看完以上两篇之后，你应该意识到这一类动态规划优化的本质都是在维护单调性。因此任何维护方法都可以用上，不要仅仅拘泥于那几种方法。

二维四边形不等式的动归优化请见《算法艺术与信息学竞赛》中相应篇目。（个人认为写的不是很好，要想半天）

状态数的减少和转移数目的减少没有特定的方法。要自己想。 如果真说有什么可以总结的方法，那就是多做预处理。

经典练习

• 01背包
• 导弹拦截
• 城市交通

链接

from Starfish

另一个意义

DP还有“地爬”的意思，即“天翔”的反义词。

如“占地爬”（JOLLWISH大牛）。 如“陈天翔”（恒元祥大牛）。