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