动态规划 用于求解最优化子问题的，往往是高效的而准确的。这背后的逻辑，其实就是程序设计的最基本原理——不要让程序做重复的事情。
一句话说算法
对于一个复杂的问题，可以分解成若干个子问题来解决，这是分治法。每个分解的子问题，得到最优解，再通过一个方式组合这些最优解，得到全局最优解，这是贪心法。而其实分解的子问题，往往会有许多重复的子问题，对程序进行减枝机制地优化，这是动态规划法。
斐波那契数列
大学课堂上，讲C语言课程的老师，一定讲过斐波那契数列。
通俗的话讲，这个数列中的第2项（从零开始计数）之后的每一项，是前两项之和。基础项，也就是第0项是0，第1项是1，以此类推得出的一个数列：
0,1,1,2,3,5,8,13,21...
朴素算法的实现是：
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n-1) + (n-2)
这个递归算法有大量的重复步骤，例如：fib(3) = fib(2) + fib(1), fib(4) = fib(3)+fib(2)。这两个步骤中fib(2)就是被重复计算了，这样的算法固然正确，但是效率太对。数据量增大，算法的时间复杂度也是指数级增大。
为了避免重复的计算操作，可以将分解的子问题的解，用一个字典存起来。每次判断如果字典中已经有了计算过得值，则不再进行计算，直接取值就可以了。这样便大大减少了算法的计算量，下面是我用python的实现：
d = {}
def fib(n):
if(n==0):
d[n] = 0
return 0
if(n==1):
d[n]=1
return 1
if not d.has_key(n) :
d[n] = fib(n-1) + fib(n-2)
return d[n]
