【数据结构（邓俊辉）学习笔记】绪论05——动态规划

0.前言

make it work,make it right,make it fast.
让代码能够不仅正确而且足够高效地运行。

1. Fibonacci数应用

1.1 fib（）：递归

1.1.1 问题与代码

上述fib()算法运行地较慢

__int64 fib ( int n ) { //计算Fibonacci数列的第n项（二分递归版）：O(2^n)
   return ( 2 > n ) ?
          ( __int64 ) n //若到达递归基，直接取值
          : fib ( n - 1 ) + fib ( n - 2 ); //否则，递归计算前两项，其和即为正解
}
1
2
3
4
5

CPU资源未被占满，进程在满负荷运行，但是依然运行地非常非常慢。

1.1.2 复杂度分析

上述推导看复杂度为指数（$2^n$）
估算下
${\varphi }^{43}$ = $2^{30}$ = $10^9$flo = 1 sec(计算工作量大概可以用10地9次方条基本操作指令来度量，10的9次方就是现在主流计算机主频的cpu在1s中大致能够吞吐的计算量，亦是fib(43)计算大概需要1s)

1.1.3 递归分析

使用第二种手段对上述代码进行分析

**每个递归实例从原理上来讲只需要计算一次。**诀窍和改进放在也在于此。

1.2 fib（）：迭代

方法A：
将Fibonacci数的各项所计算的结果制作成一个表格，将每项计算结果存入表中，每次需要递归实例的时候便可以查表获取。智能屏蔽此次和后续调用。在O(1)时间内返回结果。
方法B：
计算方向为自小而大，自底而上，这样由原来的递归算法改进为迭代型算法，同样可以完成刚才工作。如果比作上楼梯，那么在每个台阶上只需停留一次。

例如fib(5)：
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)
f(3) = f(2) + f(1)
f(2) = f(1) + f(0)
f(1) = f(0) + f(-1)
迭代的计算是自底而上，所以是算f(1) f(2) f(3)f(4) f(5)
g = g+f 等同于 f(1) = f(0) + f(-1) 再迭代
g = g+f 等同于 f(2) = f(1) + f(0) ，
这次f(0)是未知的，所以f = g-f就是算出下次迭代的末项f(0)
f(0) = f(1) - f(-1) 等同于 f = g-f

具体的代码分析可以参考Fibonacci数