什么是动态规划？动态规划的意义是什么？
动态规划是用来求解最优化问题的一种方法。常规算法书上强调的是无后效性和最优子结构描述，这套理论是正确的，但是适用与否与你的状态表述有关。至于划分阶段什么的就有些扯淡了：动态规划不一定有所谓的阶段。其实质是状态空间的状态转移。下面的理解为我个人十年竞赛之总结。基本上在oi和acm中我没有因为动态规划而失手过。所有的决策类求最优解的问题都是在状态空间内找一个可以到达的最佳状态。搜索的方式是去遍历每一个点，而动态规划则是把状态空间变形，由此变成从初始到目标状态的最短路问题。依照这种描述：假若你的问题的结论包含若干决策，则可以认为从初始状态（边界条件）到解中间的决策流程是一个决策状态空间中的转移路线。前提是：你的状态描述可以完整且唯一地覆盖所有有效的状态空间中的点，且转移路线包含所有可能的路径。这个描述是包含动态规划两大条件的。所谓无后效性，指状态间的转移与如何到达某状态无关。如果有关，意味着你的状态描述不能完整而唯一地包括每一个状态。如果你发现一个状态转移有后效性，很简单，把会引起后效性的参数作为状态描述的一部分放进去将其区分开来就可以了；最优子结构说明转移路线包含了所有可能的路径，如果不具备最优子结构，意味着有部分情况没有在转移中充分体现，增加转移的描述就可以了。最终所有的搜索问题都可以描述成状态空间内的状态转移方程，只是有可能状态数量是指数阶的，有可能不满足计算要求罢了。这样的描述下，所有的动态规划问题都可以转变为状态空间内大量可行状态点和有效转移构成的图的从初始状态到最终状态的最短路问题。于是乎，对于动态规划，他的本质就是图论中的最短路；阶段可以去除，因为不一定有明确的阶段划分。
泰硕安诚
2024-09-05 广告
动态规划一般来说是“高效”的代名词，因为其解决的问题一般退而求其次的算法只有搜索了。以“数字三角形”一题为例子，在“三角矩阵”中找一条从上到下的路径，使得权值之和最小。如果使用暴力搜索的算法，那么需求穷举出2^(n-1)条路径（n为三角形高度），而使用动态规划的话，则时间复杂度降低到了n^2，完成了质的飞跃。那么究竟为什么这么快呢？原因在于动态规划算法去掉了“无用和重复的运算”。在搜索算法中，假如从A->B有2条路径，一条代价为10，另外一条代价为100，B->终点有1024条路径。当我们选择了代价为10的那条路径走到B时，可以继续往下走完1024条路径到终点，但是在此之后，我们再从代价为100的路径从A走到B时，我们可以发现此时无论如何走，都不可能有刚才从10的路径走过来更好，所以这些计算是“无用”的计算，也可以说是“重复”的计算。这就是动态规划之所以“快”的重要原因。
动态规划是一种思维方法，整个学科的基本思想就是一条，动态规划之父Bellman的Principle of Optimality (翻译成“最优化原理”)：设想你想要采用最优的策略解决某件事，而且这件事可以分成好多步；假设你已经知道了做这件事的整体上最优的策略；再假设你根据这个整体最优策略走了几步，接下来剩下的几步的你重新算了一个最优子策略，如果和整体最优策略在接下来这几步的子策略相符合，那么这件事符合最优化原理；然后就可以使用动态规划的算法解决，解决思路就是一步步找出这些最优的子策略，最后得到整体最优策略。
