动态规划与斐波那契数列
1. 什么是动态规划（DP）
Dynamic programming is a technique to solve the recursive problems in more efficient manner. Many times in recursion we solve the sub-problems repeatedly. In dynamic programming we store the solution of these sub-problems so that we do not have to solve them again, this is called Memoization.
So the two components of dynamic programming (DP) are:
- Recursion – Solve the sub-problems recursively
- Memoization – Store the solution of these sub-problems so that we do not have to solve them again
动态规划是一种更有效地解决递归问题的技术。在递归中，我们多次重复地解决子问题。在动态规划中，我们存储这些子问题的解，这样我们就不必再次求解它们，这称为记忆。
所以，动态规划算法（DP）的两个方面是：
- 递归 - 递归地解决子问题
- 记忆化 – 存储这些子问题的解决方案，这样我们就不必再次解决它们
下面以斐波那契数列举例说明。
2. 斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、…… 这个数列从第3项开始，每一项都等于前两项之和。
更多可以参考生命曲线与神圣的斐波那契数列
斐波那契数列的定义如下：
Fibonacchi(N) = 0 for n=0
Fibonacchi(N) = 1 for n=1
Fibonacchi(N) == Fibonacchi(N-1)+Finacchi(N-2) for n>1
3. 一般递归函数的解法
#include <iostream>
using namespace std;
unsigned long long fibRecursion(int n)
{
if(n<=1) return n;
return fibRecursion(n-1) + fibRecursion(n-2);
}
int main()
{
int n;
cin >> n; //输入0~93之间的数，大于42就非常慢了
cout << fibRecursion(n) << endl;
return 0;
}
这个程序的性能很差，可以拷贝执行一下。当输入的数值（例如50）很大时，要非常久才能出结果。根据后面的时间预估，执行时间是以2的指数增长的。
从上图我们可以看到，计算Fibonacci(4) 需要计算 Fibonacci(3) 和 Fibonacci(2)。计算 Fibonacci(3)，需要计算 Fibonacci (2) 和 Fibonacci (1)，其中Fibonacci(2)在计算Fibonacci(4)已经计算过了。因此，我们一次又一次地解决许多子问题。
【思考一下】计算Fibonacci(5)的话，总共会计算多少次Fibonacci(2)？
这个实现的时间复杂度：
4. 使用动态规划
存储子问题结果，这样您就不必再次计算。存储子问题结果的方法：
- 自下而上
- 自上而下
4.1 Bottom-Up
假设我们需要解决N的问题，我们开始用尽可能小的输入来解决问题，并将其存储起来以备将来使用。现在，当您计算较大的值时，使用存储的解决方案（较小问题的解决方案）。
Bottom-Up solution for Fibonacci Series:
#include <iostream>
using namespace std;
unsigned long long fib[101];
unsigned long long fibBottomUp(int n)
{
fib[0] = 0;
fib[1] = 1;
for (int i = 2; i < n + 1; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
}
return fib[n];
}
int main()
{
int n;
cin >> n; //输入0~93之间的数
cout << fibBottomUp(n) << endl;
for (int i =0; i<=n; i++){
cout << fib[i] << " ";
}
return 0;
}
时间复杂度：O(n) ，空间复杂度： O(n)
执行效率很高，输入90也可以很快算出来。
4.2 Top-Down
将问题分解为子问题，根据需要解决它们，并存储解决方案以备将来使用。
#include <iostream>
using namespace std;
unsigned long long fib_series[101] = {0};
unsigned long long fibUpDown(int n)
{
if(n==0) return 0;
if(n==1) return 1;
if(fib_series[n]!=0) return fib_series[n];
fib_series[n] = fibUpDown(n-1) + fibUpDown(n-2); //递归计算
return fib_series[n];
}
int main()
{
int n;
cin >> n; //输入0~93之间的数
cout << fibUpDown(n) << endl;
for (int i =0; i<=n; i++){
cout << fib_series[i] << " ";
}
return 0;
}
可以比较和原来的递归算法（也是Top-Down的思路）的写法上的区别。
5. 动态规划的适用性
为了确定问题是否可以通过应用动态规划来解决，我们检查了两个属性。若问题具有这两个性质，那个么我们可以使用动态规划来解决这个问题。
- 重叠子问题
- 最优子结构。
重叠子问题，顾名思义，子问题需要一次又一次地解决。在递归中，我们每次都解决这些问题，而在动态规划中，我们只解决这些子问题一次，并将其存储起来以备将来使用。正如我们上面所看到的，我们正在反复解决许多子问题。
最优子结构：如果一个问题可以用子问题的解来解决，那么我们说这个问题具有最优子结构性质。