什么是动态规划？动态规划的意义是什么？
-
动态规划不是个具体的算法，是一个框架。框架是死的，但框架里填什么全看人。这个框架就是有向无环图。图中每个点都存着一个值。你去把图论刷一遍，弄弄拓扑排序之后，就会明白，动态规划就是对图中所有点执行拓扑排序，再依照拓扑序让每个点更新自己指向的节点的值的过程。至于图中点怎么定义，边怎么定义，值怎么定义，“更新”怎么定义，那就是考验建图论模型的能力了，我也没能力讲出个系统规律来。这时候动态规划那些概念都能一一对应了。所谓最优子结构就是我可以证明只要按着拓扑序来更新，保证能得到最优解。无后效性呢，就是图不能有环。至于记忆化嘛，就是在每个点上存一个值了。递推嘛就是把拓扑序正着来一遍，递归嘛就是把拓扑序反着来一遍。都没什么新鲜东西的。值得一提的是，根据上述的定义，动态规划不如最短路径强劲（觉得不好理解的请看后面的更新）。因为最短路径可以反复迭代，而动态规划必须一遍扫完。也就是说，不要管什么动态规划了，只要是动态规划，最短路径都能解：）动态规划点里的值嘛就是最短距离了，一个点对另一个点的更新嘛就是最短路径的更新了。若是连最短路径也不能活学活使，那还是背背书让老师开心就行了。
-
动态规划只是一个优化而已，它是通过保存那些已经求过值的状态来做到的（避免了重复计算）。很多人提到局部最优结构，但这其实不是必须的。实际情况是只要你的状态重叠足够多，重复对状态求值的代价足够高，你就应该考虑对状态做cache。讽刺的是，动态规划就是指这个cache的过程。基本没太多技术含量，因为问题的根本在于状态怎么转移。而我们之所以尝试分析最优子结构，也是为了找到一个好的状态表示（但并不是所有问题都能用所谓最优子结构来构造的）。
-
动态规划，就是把计算过程中产生的中间结果静态地保存起来，后面再用到这些中间结果的时候就不用再算一遍，而是直接读取。那明明是静态规划为什么要叫动态？其实据发明这个名字的Bellman教授讲：当时他所在的公司给美国军方打工，军方管他们的头头是个大老粗，属于那种“对‘研究’、‘数学’之类的词汇有病理性的恐惧与憎恶”的那种人，于是机智的Bellman决定不告诉他自己在公司里是研究数学的。他给自己的工作安了个名称叫“动态编程dynamicprogramming”（翻译成中文时翻成了规划）。为什么叫“动态（dynamic）”呢？Bellman说，除了很恰当地描绘了自己的工作以外，“动态”还是一个神奇的词：它不可能被应用于贬义的语境！你试试用它造个含贬义的句子，造不出来吧？这是一个连政客都挑不出刺的词，所以Bellman用它给自己的研究打掩护。
-
首先，动态规划是一种算法。那么，何谓算法？计算机书籍中不难找到其严谨的学术定义，大众可以简单理解为“解决某一类问题的核心思想”。先谈动态规划的意义——望文生义，“动态”规划对应“动态”的问题：你并不知道问题的规模会有多大，而不论是个位数还是百万级，都能以较快速度(动态规划是一种泛用性算法，而泛用性算法与特定算法相比往往存在性能差距)将结果正确计算出来。这是对于计算机科学最直观的意义，当然我认为其对人生亦有一定指导意义，但那是见仁见智的事了。动态规划这一思想的实质其实是以下两点：1.分析问题，构造状态转移方程2.以空间换时间
-
首先明确：动态规划是用来求解最优化问题的一种方法。常规算法书上强调的是无后效性和最优子结构描述，这套理论是正确的，但是适用与否与你的状态表述有关。至于划分阶段什么的就有些扯淡了：动态规划不一定有所谓的阶段。其实质是状态空间的状态转移。下面的理解为我个人十年竞赛之总结。基本上在oi和acm中我没有因为动态规划而失手过。所有的决策类求最优解的问题都是在状态空间内找一个可以到达的最佳状态。搜索的方式是去遍历每一个点，而动态规划则是把状态空间变形，由此变成从初始到目标状态的最短路问题。依照这种描述：假若你的问题的结论包含若干决策，则可以认为从初始状态（边界条件）到解中间的决策流程是一个决策状态空间中的转移路线。前提是：你的状态描述可以完整且唯一地覆盖所有有效的状态空间中的点，且转移路线包含所有可能的路径。这个描述是包含动态规划两大条件的。所谓无后效性，指状态间的转移与如何到达某状态无关。如果有关，意味着你的状态描述不能完整而唯一地包括每一个状态。如果你发现一个状态转移有后效性，很简单，把会引起后效性的参数作为状态描述的一部分放进去将其区分开来就可以了；最优子结构说明转移路线包含了所有可能的路径，如果不具备最优子结构，意味着有部分情况没有在转移中充分体现，增加转移的描述就可以了。最终所有的搜索问题都可以描述成状态空间内的状态转移方程，只是有可能状态数量是指数阶的，有可能不满足计算要求罢了。这样的描述下，所有的动态规划问题都可以转变为状态空间内大量可行状态点和有效转移构成的图的从初始状态到最终状态的最短路问题。于是乎，对于动态规划，他的本质就是图论中的最短路；阶段可以去除，因为不一定有明确的阶段划分。
-
动态规划的本质不在于是递推或是递归，也不需要纠结是不是内存换时间。理解动态规划并不需要数学公式介入，只是完全解释清楚需要点篇幅…首先需要明白哪些问题不是动态规划可以解决的，才能明白为神马需要动态规划。不过好处时顺便也就搞明白了递推贪心搜索和动规之间有什么关系，以及帮助那些总是把动规当成搜索解的同学建立动规的思路。当然熟悉了之后可以直接根据问题的描述得到思路，如果有需要的话再补充吧。动态规划是对于某一类问题的解决方法！！重点在于如何鉴定“某一类问题”是动态规划可解的而不是纠结解决方法是递归还是递推！怎么鉴定dp可解的一类问题需要从计算机是怎么工作的说起…计算机的本质是一个状态机，内存里存储的所有数据构成了当前的状态，CPU只能利用当前的状态计算出下一个状态（不要纠结硬盘之类的外部存储，就算考虑他们也只是扩大了状态的存储容量而已，并不能改变下一个状态只能从当前状态计算出来这一条铁律）当你企图使用计算机解决一个问题是，其实就是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。所以所谓的空间复杂度就是为了支持你的计算所必需存储的状态最多有多少，所谓时间复杂度就是从初始状态到达最终状态中间需要多少步！太抽象了还是举个例子吧：比如说我想计算第100个非波那契数，每一个非波那契数就是这个问题的一个状态，每求一个新数字只需要之前的两个状态。所以同一个时刻，最多只需要保存两个状态，空间复杂度就是常数；每计算一个新状态所需要的时间也是常数且状态是线性递增的，所以时间复杂度也是线性的。上面这种状态计算很直接，只需要依照固定的模式从旧状态计算出新状态就行（a[i]=a[i-1]+a[i-2]），不需要考虑是不是需要更多的状态，也不需要选择哪些旧状态来计算新状态。对于这样的解法，我们叫递推。非波那契那个例子过于简单，以至于让人忽视了阶段的概念，所谓阶段是指随着问题的解决，在同一个时刻可能会得到的不同状态的集合。非波那契数列中，每一步会计算得到一个新数字，所以每个阶段只有一个状态。想象另外一个问题情景，假如把你放在一个围棋棋盘上的某一点，你每一步只能走一格，因为你可以东南西北随便走，所以你当你同样走四步可能会处于很多个不同的位置。从头开始走了几步就是第几个阶段，走了n步可能处于的位置称为一个状态，走了这n步所有可能到达的位置的集合就是这个阶段下所有可能的状态。现在问题来了，有了阶段之后，计算新状态可能会遇到各种奇葩的情况，针对不同的情况，就需要不同的算法，下面就分情况来说明一下：假如问题有n个阶段，每个阶段都有多个状态，不同阶段的状态数不必相同，一个阶段的一个状态可以得到下个阶段的所有状态中的几个。那我们要计算出最终阶段的状态数自然要经历之前每个阶段的某些状态。好消息是，有时候我们并不需要真的计算所有状态，比如这样一个弱智的棋盘问题：从棋盘的左上角到达右下角最短需要几步。答案很显然，用这样一个弱智的问题是为了帮助我们理解阶段和状态。某个阶段确实可以有多个状态，正如这个问题中走n步可以走到很多位置一样。但是同样n步中，有哪些位置可以让我们在第n+1步中走的最远呢？没错，正是第n步中走的最远的位置。换成一句熟悉话叫做“下一步最优是从当前最优得到的”。所以为了计算最终的最优值，只需要存储每一步的最优值即可，解决符合这种性质的问题的算法就叫贪心。如果只看最优状态之间的计算过程是不是和非波那契数列的计算很像？所以计算的方法是递推。既然问题都是可以划分成阶段和状态的。这样一来我们一下子解决了一大类问题：一个阶段的最优可以由前一个阶段的最优得到。
回答请先登录