https://leetcode.com/problems/climbing-stairs/

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Idea:

Solution:

C = C(N - 2) + C(N - 1)

C(1) = 1
C(2) = 2

class Solution {

public:
    int climbStairs(int n) {
        if (n == 1)
            return 1;

        int first = 1, second = 2;
        for(int i = 3; i <= n; ++i) {
            int third = first + second;
            first = second, second = third;
        }

        return second;
    }
};

Complexity Analysis:

Time

O(N)

Memory

1