1 .简介动态规划Dynamic Programming:这里的“编程”不是写程序代码，而是表计算法(A tabular method )，基于表查询的方法是最优的
动态规划与分治法(The Divide-and-Conquer Method )有点相似，但也是将问题分解为多个子问题，并基于子问题的结果得到最终解。 两者的区别在于，分治法将初始问题分割为多个不相关(Disjoint )子问题(Subproblem )，即递归求解子问题，然后合并子问题的解得到初始问题的解。 与此相对，通过动态规划法分解的部分问题相互重叠，即部分问题依赖于部分问题(Subsubproblem )，部分问题又依赖于下一个部分问题，这样一直循环到不需要分解的初始条件。 在求解过程中，为了避免重复计算子问题以提高算法的效率，需要将一系列子问题的解保存在一张表中。 (table，c编程一般采用std:array、std:vector或std:list实现。 这也称动态规划为查找表计算法
动态规划通常应用于优化问题。 这类问题一般存在多个解，每个解都有度量值，并且要求度量值最好(即取最大或最小值)的解。 该最优解一般称为优化问题的一个解。 请注意，此解不是唯一的，因为优化问题可能存在多个最优解。
通过例子说明如何理解DP 2.1。 很容易理解，所以先看看生活中经常遇到的事情吧。 ——假设你是一个朴素的杯子，有足够的面额为1、5、10、20、50、100元的钞票。 现在你的目标是挤出某个金额w，需要使用尽可能少的纸币。
从生活经验来看，我们显然可以采取这样的策略。 能用100的尽量用100，否则尽量用50……依次类推。 在这个战略下，666=6100 150 110 15 11，共计使用了10张纸币。
这个战略被称为“贪婪”。 假设我们面临的情况是“需要收集w”，贪婪策略会尽快缩小w。 如果w能减少100，就能尽量减少100。 这样的话，我们接下来面临的局面就是收集w-100。 长期的生活经验表明，贪婪策略是正确的。
但是，如果我们改变纸币面值，贪婪战略可能就不成立。 如果奇怪的国家纸币面值分别是1、5、11，我们出15的时候，贪婪策略是错误的。
15=111 41 (贪婪策略使用了5张纸币) ) ) ) ) ) ) ) ) ) ) ) ) )。
15=35 (正确的战略，只有三张钞票) ) ) ) ) ) )。
为什么会这样呢？ 贪婪策略在哪里错了？
鼠一般的眼神。
正如我刚才提到的，贪婪战略的纲领是“尽量减小今后面临的w”。 这样，贪婪策略在w=15的局面下，优先使用11将w降低到4，但是在这个问题上，收集4的成本很高，必须使用41。 使用5时，w下降到10。 虽然没有4那么小，但是出10只需要2张5元。
这里明白了，贪婪是只考虑眼前状况的策略。
那么，怎样才能避开老鼠的眼睛呢？
如果直接用暴力找出w的方案，显然复杂度太高了。 可以用太多的方法收集w，列举它们的时间让人难以忍受。 在这里找找性质吧。
重新分析刚才的例子。 w=15时，如果我们取11，接下来就会面临w=4的情况； 如果取5，接下来就会面对w=10的情况。 我发现这些问题有同样的形式。 “给w，用来提取w的最低纸币是几张？ ”然后，用F(N )表示“挤出n所需的最小纸币数”。
那么，如果我们拿了11，最后的代价(用过的纸币总数)是多少呢？
很明显什么是动态计划？ 动态规划的意义是什么？这个意思是，利用11收集15的话，f(4)就会加上自己这个牌。 现在，我们不管f(4)怎么求都没关系。
依次类推的话，马上就会明白，如果用5聚集15，则cost可以是f(10 )=2)1=3。
那么，现在w=15的时候，我们应该拿那样的纸币吗？ 当然是在各种方案中，cost值最低的那个！
很明显，cost值最低的是取5的方案。 我们通过上面的三个公式，做出了正确的决定！
这给了我们非常重要的启示：
这个仪式非常令人兴奋。 我们要求给出f(n )，只需要求出一些更小的f值； 那么，我们从小到大的f(I )不就可以了吗？ 请注意边界的状况。 代码如下所示。
这两个事实，保证了我们做法的正确性。 比起贪婪策略，我们可以分别计算出1、5、11的成本，做出正确的决策，从而避免“鼠目寸光”！
和暴力的区别在哪里？ 我们的暴力列举了“被使用的硬币”，这是冗长的信息。 我们要的是答案，我完全不在乎这个答案是怎么聚集起来的。 例如，对于推出f(15 )，仅仅需要知道f ) 14 )、f ) 10 )和f )4)的值。 不需要其他信息。 我们放弃了冗长的信息。 我们只记录了有助于解决问题的信息——f(n )。
我们能这样做，主要取决于问题的性质。 求f(n )只需要知道几个更小的f。 求解f称为求解f(n )的“子问题”。
这就是动态规划(DP )。 一个
问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。 2.2 如何理解DP的几个重要性质 【无后效性】一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。
要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。
“未来与过去无关”， 这就是 无后效性 。
（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）
回顾我们对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n).
f(n)的定义就已经蕴含了“最优”。 利用w=14,10,4的 最优 解，我们即可算出w=15的 最优 解。
大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。
一言以蔽之：大事化小，小事化了。
将一个大问题转化成几个小问题；
求解小问题；
推出大问题的解。
下面介绍比较通用的设计DP算法的步骤。
首先，把我们面对的局面表示为x。这一步称为设计状态。对于状态x，记我们要求出的答案(e.g. 最小费用)为f(x).我们的目标是求出f(T).找出f(x)与哪些局面有关（记为p），写出一个式子（称为状态转移方程），通过f(p)来推出f(x). 2.4 DP的典型应用：DAG最短路有向无环图DAG(Directed acyclic graph): 如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图。
求图中节点的单源最短路径可以使用Dijkstra,BellmanFord, 算法，而对于有向无环图DAG来说，可以通过简单的动态规划来进行求解。 DAG的独特之处是所有节点可以线性化（拓扑序列），使得所有边保持从左到右的方向.
问题很简单：给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。
边上的数字表示过路费。
这个问题能用DP解决吗？我们先试着记从S到P的最少费用为fp
想要到T，要么经过C，要么经过D。从而
好像看起来可以DP。现在我们检验刚刚那两个性质：
那肯定S走到Q的最优路径是:
对一条最优 的路径而言，从S走到 沿途上所有的点（子问题） 的最优路径，都是这条大路的一部分。这个问题的最优子结构性质是显然的。
既然这两个性质都满足，那么本题可以DP。 式子明显为：
a.单源最短路径
从一个点出发，到达其他顶点的最短路径的长度。基本操作：**松弛**d[u]+map[u, v]< d[v]这样的边(u,v)称为紧的(tense),可以对它进行松弛(relax):d[v] = d[u]+w, pred[v] = u最开始给每一个点一个很大的d值，从d[s]=0开始，不断的对可以松弛的点进行松弛，不能松弛的时候就已经求出了最短路了b.Floyd算法
多源，基于动态规划，本质上是一个三维的DP, 与其他算法不同，floyd是一个多源最短路径算法，即经过 一次floyd后能求出任意两点间的最短路径c.Dijkstra
单源，只适用于**无负边权**的图, 可以包含环d. Bellman-ford算法
单源，基于动态规划, 边权可正可负, 可以包含环, 可以用来判负环 3. DP在Apollo项目规划模块中的应用Apollo项目Planning模块的EMPlanner中使用动态规划生成代价（Cost）最小的多项式路径（DP路径，见Apollo项目中的DPRoadGraph类）和速度（DP速度，见Apollo项目中的DpStGraph类），DP路径算法和DP速度算法的示意性描述如下图所示
DP路径算法的基本思路是，基于给定的一条中心路径（称为参考线，ReferenceLine）和车道边界条件，每隔一定间隔的纵向距离（称为不同级（Level）上的s值）对道路截面进行均匀采样（与中心点的横向偏移值称为为l值），这样会得到图中黑点所示的采样点（这些采样点称为航点，Waypoint）数组。基于一定的规则，可以给出各航点迁移的代价值（Cost）。航点迁移不一定需要逐级进行，可以从第一级跳到第三级甚至终点，只要迁移代价值最小化即可，这显然满足动态规划的求解思路。
DP速度算法的基本思路是，在DP路径算法生成一条可行驶的路径后，从起点开始，考虑避开路径中的所有障碍物，并且让加减速最为平顺，以最优的速度曲线（即t-s平面中的绿色曲线）安全抵达终点，这也可以使用动态规划的思路求解。
参考文献：
算法-最短路径：DAG、Dijkstra、Bellman-Ford
什么是动态规划（Dynamic Programming）？动态规划的意义是什么？
动态规划及其在Apollo项目Planning模块的应用