aboutsummaryrefslogtreecommitdiff
path: root/climbing_stairs.cpp
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);
}