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
