## Problem Description:

A baby wants to climb the stairs. It can take a single step at a time or take 2 steps at a time. Or it can take a combination of 1 and 2 steps at a time.

Given that there are N stairs, find the number of ways the baby can reach the top of the stairs.

## Solution Diagram:

Suppose there are 3 steps, there can be 3 ways the baby can reach the top of the stairs. Below is the diagram to explain the same.

One Step at a time

Two-step then one step

One step then Two-step

## More Example:

If steps = 1 Only 1 way

If steps = 2 (1, 1), (2) 2 ways.

If steps = 4 (1, 1, 1, 1), (2, 2), (1, 1, 2), (2, 1, 1), (1, 2, 1) 5 ways.

In a way, this is equal to Fibonacci series. Here if there are N steps, then the number of ways to climb will be Fibonacci(N + 1)

## Solution in C language:

#include<stdio.h> int calculate_fibonacci(int num) { if (num <= 1) return num; return calculate_fibonacci(num - 1) + calculate_fibonacci(num - 2); } int get_number_of_ways(int stairs) { return (calculate_fibonacci(stairs + 1)); } int main(int argc, char const *argv[]) { int no_of_stairs = 0; int no_of_ways = 0; printf("Please enter number of stairs\n"); scanf("%d", &no_of_stairs); no_of_ways = get_number_of_ways(no_of_stairs); printf("The number of ways the baby can climb is %d \n",no_of_ways ); return 0; }

### Output:

Please enter number of stairs 4 The number of ways the baby can climb is 5