[Google Question] Climbing Stairs

Problem: You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Approach: We can use DP here as if you see it is kind of fibonacci number problem so instead of maintaining a table we can use three variables. Have a look at the implementation to understand the approach better.

Implementation in C#:

        public int ClimbStairs(int n)

        {

            if (n <= 2)

            {

                return n;

            }

            // Could build the whole DP table but is not required. Kind of fibonacci number

            int c0 = 1;

            int c1 = 2;

            int cn = 0;

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

            {

                cn = c0 + c1;

                c0 = c1;

                c1 = cn;

            }

            return cn;

        }

Complexity: O(n)