leetcode

0 // memorization approach

1 class Solution {

2 public:

3 int fib(int n) {

4 vector<int> f(31);

5 f[0] = 0;

6 f[1] = 1;

7 for (int i = 2; i <= n; i++)

8 f[i] = f[i - 1] + f[i - 2];

9 return f[n];

10 }

11 };

12

13 // optimized, memorize only the previous two values

14 class Solution {

15 public:

16 int fib(int n) {

17 if (n == 0) return 0;

18 int a = 0, b = 1;

19 for (int i = 2; i <= n; i++) {

20 int tmp = a + b;

21 a = b;

22 b = tmp;

23 }

24 return b;

25 }

26 };