求Fibonacci数列的第i个数，最直接方法是直接根据Fibonacci的Formulating a relation among the states，即前后状态关系方程，编码递归函数实现，注意递归的终止条件是当自身传进来的参数n==1或者0时，就return 1或者0，若不是，则继续执行调用下面的本身函数进行递归调用。但其时间复杂度是指数级别：T(n)=T(n-1)+T(n-2)，请问，根据该公式如何计算递归的时间复杂度？
那么，如何提高计算效率了？我们观察递归关系式，发现有很多中间项是共用的，而在计算时被重复计算，因此我们想到存储中间已经计算过的值，则想到了dynamic Programming(DP算法)，那么如何保存中间参数，减少重复计算的过程呢？首先根据DP的memorize思想，用一个向量memorize来存储已经计算过的值。那如果判断该值是否已经被计算过呢？方法是先将向量memorize中的值初始化为不同于递归求解过程中的任何值，比如全部初始化为-1，然后再调用递归函数之前，先判断第i个数memorize[i]值是否为-1，若不为-1,则说明已经计算赋值过了，就无需调用递归函数f(i)计算，若没有计算过，则调用递归函数计算f(i)的值，然后将递归返回的值赋值给memorize[i]，按照顺序对应保存即可。算法实现如下：
int DynamicProgramming::fibonacci(int n) { std::vector<int>memory; //n>=0 memory.resize(n+1); for (int i = 0; i < memory.size();i++) { memory[i] = -1; //初始值为-1，即未计算前的值 } return conquerFibonacci(n, memory); } int DynamicProgramming::conquerFibonacci(int n, std::vector<int>&memory) { int result; if (n == 1) { return 1; } if (n == 0) { return 0; } if (memory[n]!=-1) //空间换时间的策略 { result = memory[n]; //通过动态规划存储思想直接取存储的中间值 } else { result = conquerFibonacci(n - 1,memory) + conquerFibonacci(n - 2,memory); memory[n] = result; //存储中间值 } return result; }
