blob: afc3d7e9eaf5341b5d8f4f8a9e1f007301e72a33 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include "leetcode.h"
class Solution {
public:
int climbStairs(int n) {
/*
* base case
* because if 0 steps -> 0 ways,
* 1 step -> 1 way, & 2 step -> 2 ways
*/
if (n <= 2)
return n;
/*
* last step was either:
* 1 step (oneStep) or 2 steps (twoStep)
* so simply add the two values (fibonacci sequence)
*/
int oneStep = 1, twoStep = 2, ans;
for (int i = 3; i <= n; i++) { // 0-2 steps already determined
ans = oneStep + twoStep;
oneStep = twoStep;
twoStep = ans;
}
return ans;
}
};
int main() {
Solution obj;
cout << obj.climbStairs(4);
}
|