听起来高大上的“算法”，其实一点也不难！
算法思想就是解题思路，是算法程序的提纲，常见的算法思想就4种：
贪心算法（GreedyAlgorithm）
分治算法（DivideandConquer）
动态规划（DynamicProgramming）
穷举搜索（ExhaustiveSearching）
可以说90%以上的算法，都来自这4种基本思想。
前面2节课，我们讲解了贪心算法和分治算法。
而分治算法是将原问题的规模减小，变成更容易解决的问题，有时允许反复分治减规模减到很小，问题的最优解甚至达到一目了然的状态。
今天要讲的动态规划，简直是集上述两种思想之大成，又克服二者的缺点。
动态规划，英文是DynamicProgramming（DP），擅长解决“多阶段决策问题”，利用各个阶段之间的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题最优决策。
理解动态规划，可以先从名字入手。
“动态”，是指“变化的状态”，我们将怎样做决策这样的抽象问题，使用数据来定义为一个一个的状态，而这些状态是随着问题的规模而变化的。这里比较类似于分治法，问题的规模是变化的。
“规划”，英文是programming，其实不是“编程”的意思，更易于理解的翻译应该是“表格”，也就是说，上面所说的那些“变化的状态”放在一些，成为一个表格，随着问题的推进，表格会不断地更新。
动态规划往往使用表格来存储中间结果
这就是动态规划。
动态规划是基础算法中最不好理解的，咱们先从一个最简单的小问题慢慢讲解。
问题：一个10级的台阶，每次只能上1级或2级，问题共有几种上法？
读者可以先自己思考一下，这其实就是一类最简单的多阶段决策问题。
每一步上几级台阶，都是一个决策
其实，我们可以先把问题倒着想一下：
最后一次决策，也就是完成10级台阶的最后一步，要么是从第8级迈2级上来，要么就是从第9级迈1级上来的，所以也就是说，有多少种办法上8级，再加上有多少种办法上9级，就是完成10级台阶的方法总和。
如果用F(n)表示上n级台阶共有多少种方法，那么上面的推理表示为：
F(10)=F(9)+F(8)
说到这里，我们发现：
1将求F(10)这个问题，完美的分解成了F(9)和F(8)，找到了局部的最优解，与贪心算法有点像；
2既然F(10)=F(9)+F(8)，那么F(9)=F(8)+F(7)，依此类推，最终问题被逐渐降低了规模，越来越简单，这又是分治的思想；
到这里我想大家对这个问题已经知道大概怎么做了，我们借助这个问题总结一下：
F(10)=F(9)+F(8)，就是F(10)问题的最优子问题，局部的贪心完美的将问题分解，如果得到的F(9)和F(8)都是最优解，那么F(10)一定是最优解。
分解到最后，一定是变成了规模最简单的问题，即F(1)和F(2)，这两个问题不能再分解了，不过没关系，他们很简单，心算就搞定了。
本问题的状态转移方程为：F(n)=F(n-1)+F(n-2)，这是解决问题的核心，是状态能够“动态”起来的原因。
一个典型的二叉树结构
不过仔细一看，就会发现，有好多中间结果是重复的！
相同颜色的部分其实是相同的结果
这就好办了，把计算过的中间结果都存起来呗，如果再次遇到计算过的问题，就直接去查询！
这个存储中间结果的的表，叫做——
备忘录。
上面的算法很不错了，不过并不完全是动态规划的思路，我们需要将思路再倒过来：
从初始的边界条件F(1)和F(2)开始，使用状态转移方程，不就能更快地推导出结果么！
就是这么简单！
每一个格子，其实就是一个状态，随着阶段的进行，这个状态格会不断更新，这就是动态规划。
上面的例子，看起来有点像分治法啊，那么它们之间的区别在哪里？
其实，动态规划最大的特点，在于状态转换方程中，子问题是“有重叠的”，这也是动态规划的意义所在，如果没有重叠，也就不存在上面所说的减小计算量的优势了，那么就退化成分治法了。
重复计算要努力避免
所以说，状态转换方程（DP方程）就是算法的核心，那么设计DP方程，有什么要注意的？
从上面的算法三要素中，可以看出，DP方程是从最优子问题中归纳而来的。
那么，什么才算“最优子问题”呢？
就是说，不管之前决策是否是最优决策，都必须保证从现在开始的决策是在之前的基础上最优。具体的说，我们默认F(8)和F(9)就是最优的，在此基础上，得到最优的F(10)。