动态规划不是个具体的算法，是一个框架。框架是死的，但框架里填什么全看人。

这个框架就是有向无环图。图中每个点都存着一个值。你去把图论刷一遍，弄弄拓扑排序之后，就会明白，动态规划就是对图中所有点执行拓扑排序，再依照拓扑序让每个点更新自己指向的节点的值的过程。

至于图中点怎么定义，边怎么定义，值怎么定义，“更新”怎么定义，那就是考验建图论模型的能力了，我也没能力讲出个系统规律来。

这时候动态规划那些概念都能一一对应了。所谓最优子结构就是我可以证明只要按着拓扑序来更新，保证能得到最优解。无后效性呢，就是图不能有环。至于记忆化嘛，就是在每个点上存一个值了。递推嘛就是把拓扑序正着来一遍，递归嘛就是把拓扑序反着来一遍。都没什么新鲜东西的。

值得一提的是，根据上述的定义，动态规划不如最短路径强劲（觉得不好理解的请看后面的更新）。因为最短路径可以反复迭代，而动态规划必须一遍扫完。

也就是说，不要管什么动态规划了，只要是动态规划，最短路径都能解：）动态规划点里的值嘛就是最短距离了，一个点对另一个点的更新嘛就是最短路径的更新了。

若是连最短路径也不能活学活使，那还是背背书让老师开心就行了。