这样我们可以画出路线图，如下图右边表格：
这个例子的分析和解决方法大概就是这样了。在前面第一个例子里面我们提到：空间换时间是动态规划的精髓。但是一个问题是否能够用动态规划算法来解决，需要看这个问题是否能被分解为更小的问题（子问题）。而子问题之间是否有包含的关系，是区别动态规划算法和分治法的所在。一般来说，分治法的各个子问题之间是相互独立的，比如折半查找（二分查找）、归并排序等。而动态规划算法的子问题在往下细分为更小的子问题时往往会遇到重复的子问题，我们只处理同一个子问题一次，将子问题的结果保存下来，这就是动态规划的最大特点。
动态规划算法总结起来就是两点：
1 寻找递推（递归）关系，比较专业的说法叫做状态转移方程。
2 保存中间状态，空间换时间。