轨迹规划-动态规划DP和最短路径问题_轨迹动态规划dp是什么

1.简介

动态规划Dynamic Programming: 这里的“Programming”并非指编写程序代码，而是指一种表格计算法（A tabular method），即基于表格查询的方法计算得到最优结果。

动态规划与分治法（The Divide-and-Conquer Method）有些类似，也是将问题分解为多个子问题，并且基于子问题的结果获得最终解。二者的区别是，分治法将初始问题划分为多个不关联（Disjoint）的子问题（Subproblem)（即子问题相互之间互不依赖），递归地解决子问题，然后将子问题的解合并得到初始问题的解。与之相反，动态规划法分解得到的子问题是相互重叠的（Overlap），即子问题依赖于子子问题（Subsubproblem)，子子问题又进一步依赖于下一级的子子问题，这样不断循环直至抵达不需分解的初始条件。在求解过程中，为了避免重复计算子子问题从而提高算法效率，需要将一系列子子问题的解保存到一张表中（table，C++编程一般使用std::array、std::vector或std::list实现），这也就是动态规划又被称为查表计算法的原因。

动态规划一般应用于最优化问题（Optimization Problems）。这类问题一般存在多个解，每个解都具有一个度量值，我们期望得到具有度量值最优（即取最大或最小值）的解。该最优解一般称为最优化问题的一个解。注意，这个解并非唯一，因为最优化问题可能存在多个最优解。

2.如何理解DP

2.1 举例说明，通俗易懂

先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。

依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。

这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪心策略是正确的。

但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别是1、5、11，那么我们在凑出15的时候，贪心策略会出错：
15=1×11+4×1 （贪心策略使用了5张钞票）
15=3×5 （正确的策略，只用3张钞票）
为什么会这样呢？贪心策略错在了哪里？

鼠目寸光。
刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。
在这里我们发现，贪心是一种只考虑眼前情况的策略。

那么，现在我们怎样才能避免鼠目寸光呢？

如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。