leetcode

0 // memorization approach

1 class Solution {

2 public:

3 int climbStairs(int n) {

4 vector<int> vec(46);

5 vec[0] = 1;

6 vec[1] = 1;

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

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

9

10 return vec[n];

11 }

12 }

13

14 // optimized, memorize only the previous two values

15 class Solution {

16 public:

17 int climbStairs(int n) {

18 int first = 1, second = 1;

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

20 int cnt = first + second;

21 first = second;

22 second = cnt;

23 }

24

25 return second;

26 }

27 };