Climbing Stairs

Problem

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?

Constraints

• 1 <= n <= 45

Solution

The problem Climbing Stairs can be solved using a dynamic programming. n steps can be taken either from n-1 step and taking 1 step or from n-2 step and taking 2 steps. Thus, number of distinct ways to take n steps is equal to the sum of distinct ways to take n-1 steps and n-2 steps. In other words, the problem Climbing Stairs is equivalent to calculating a Fibonacci number.

Implementation

class Solution
{
  public:
    int climbStairs(int n)
    {
        int num[46] = {1, 1};

        for (int i = 2; i <= n; i++)
            num[i] = num[i - 1] + num[i - 2];

        return num[n];
    }
};