动态规划
目录
动态规划
今天看到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、顺序从小往大算
从小往大算