qiaoxu123
1/12/2019 - 3:08 AM

509 Fibonacci Number

经典的Fibonacci 题目，在这重新温习一下

  • Approach 1 ： iterative

    最经典的方法，将过程进行分解求解

  • Approach 2 ： Array

    使用数组进行值的保存，使用时直接进行调用即可

iterative.cpp
content_copyfile_download
class Soultion {
public:
    int fib(int N) {
      if(N < 2) return N;
      else
        return fib(N - 1) + fib(N - 2);
    }
}
array.cpp
content_copyfile_download
//Runtime: 0 ms, faster than 100.00%

class Solution {
public:
    int fib(int N) {
        if(N < 2) return N;
        int a = 0,b = 1,c = 0;
        
        for(int i = 0;i < N;++i){
            a = b;
            b = c;
            c = a + b;
        }
        
        return c;
    }
};