我比较不长记性，你要我马上写一个动态规划给你是比较有难度的。在我眼里，动态规划就是一个优化程序的手段，适合于有大量重复子计算问题的时候用，原理就跟缓冲有点像，把需要重复计算的东西都放进内存里，需要的时候通过索引之类的东西直接查询，节省重新计算的时间。

下面来看一幅图：

假设要从 A 到 H，在这个带权图中求最短路径。那么有：

min(H)=min(min(F)+FH,min(G)+GH)

min(F)=min(min(D)+DF,min(E)+EF)

min(G)=min(min(D)+DG,min(E)+EG)

从前三步，我们可以发现，min(D)、min(E) 均是重复计算了的，那么如果将其存起来，下次计算的时候就可以节省时间了。

从这个例子可以发现，动态规划要求问题必须要有最优子结构，即原问题可以递归到规模降低的子问题进行求解。