C++ 斐波那契数列的两种实现方式

1 size_t rec_fibonacci(int idx)
2 {
3   if (0 >= idx) return 0;
4   if (2 >= idx) return idx;
5 
6   return (rec_fibonacci(idx - 1) + rec_fibonacci(idx - 2));
7 }

 1 size_t dp_fibonacci(int idx)
 2 {
 3   if (0 >= idx) return 0;
 4   if (2 >= idx) return idx;
 5 
 6   std::vector<size_t> fibonacci;
 7   fibonacci.push_back(1);
 8   fibonacci.push_back(2);
 9 
10   size_t pre_last_num, last_num, curr_num;
11 
12   pre_last_num = fibonacci[0];
13   last_num     = fibonacci[1];
14 
15   for (size_t i = 2; i < idx; ++i)
16   {
17     curr_num     = pre_last_num + last_num;
18     pre_last_num = last_num;
19     last_num     = curr_num;
20 
21     fibonacci.push_back(curr_num);
22   }
23 
24   return fibonacci[idx - 1];
25 }