动态规划

今天看到leetcode上有个求斐波那契数列的题目

（剑指offer 10-I）

刚开始使用了递归，发现超时

func fib(n int) int {
   if n == 0{
       return 0
   }else if n == 1 {
       return 1
   }
   return (fib(n - 1) + fib(n - 2)) % 1000000007
}

最后参照题解突然想到这是一个动态规划的题目

动态编程就是一种记住东西以节省时间的好方法

下面是Quora上一个高赞的回答

能用动态规划解决的问题，

1、问题的答案依赖于问题的规模，问题的所有答案构成了一个数列

​ 比如1个人有两条腿，2个人有四条腿，n个人肯定能推出来有2n条腿，腿树就可以抽象成间隔为2的等差数列（0，2，4…..2n）

2、大规模问题的答案可以由小规模问题的答案递推

​ 显然在上述问题中，腿数量可以递推出来

f（n） = f（n - 2)

适用于动态规划解决的问题

能用动态国画解决不代表很实用，比如刚刚数腿的例子，可以写成f（n） = 2n的显式表达形式，那么就没必要再推出来了，大多数场景下，f（n）并没有那么容易做到，因此要用动态规划

应用动态规划——将动态规划拆分成三个子目标

1、建立状态转移方程

​ 假装已经知道了f（1）～f（n - 1）的值，然后想办法利用他们求得f（n），在数腿的例子中，状态转移方程即为f（n）=f（n - 1） + 2

2、缓存并服用以往结果

​ 每计算一个结果，就先把结果保存下来，然后等待下次用

3、顺序从小往大算

​ 从小往大算