Fibonacci的两种解法 – 最简单的动态规划法

通过几天时间的闭关修炼,终于练成算法中的独孤九剑–动态规划法了,哈哈O(∩_∩)O哈哈~。

下面是最简单的动态规划法例子。

求 Fibonacci 数,最简单的就是利用递归求解。如下面第二个函数两行代码就可以了。

但是这样的话会不断递归,造成很多重复求解,运行速度自然很低。为了提高速度,可以把之前求解到的值保存下来,在下一次循环中重复利用。比如求F(n) = F(n-1) + F(n-2);

F(n-1) =F(n-2)+F(n-3),求F(n)的时候,如果F(n-1)的值保存了的话,那么就不用重复递归求F(n-1)了。

下面第一个函数就是这样解的,效率就是O(n)了,很高的效率。

这个就是动态规划法的入门基础,简单概括就是:如果计算的结果是后面需要重复用到的话,那么就保存这个结果。

 

[cpp][/cpp] view plaincopyprint?

  1. class Solution {
  2. public:
  3.     int fibonacciD(int n)
  4.     {
  5.         if(n==0 || n==1) return 1;
  6.         int last = 1;
  7.         int nextToLast = 1;
  8.         int answer = 1;
  9.         for(int i = 2; i<=n; i++)
  10.         {
  11.             answer = last+nextToLast;
  12.             nextToLast = last;
  13.             last = answer;
  14.         }
  15.         return answer;
  16.     }
  17.     int fibonacciR(int n)
  18.     {
  19.         if(n==0 || n==1) return 1;
  20.         return fibonacciR(n-1)+fibonacciR(n-2);
  21.     }
  22. };
  23. int main()
  24. {
  25.     Solution solu;
  26.     cout<<solu.fibonacciD(7)<<endl;
  27.     cout<<solu.fibonacciR(7)<<endl;
  28.     cout<<endl;
  29.     return 0;
  30. }

标签