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)
Since baby can take one or two steps at a time, we can create a below tree, if the number of steps is 6.
First baby can take 1 step or 2 steps.
So in the next step, we need to calculate the number of ways taken to raise 5 steps and 4 steps.
We can build full tree for the steps taken as below:
This problem can be solved by:
- Recursion
- Top Down Memoization
- Bottom Up tabular method.
1. Recursion:
In the recursion, we take the number and then recursively call the function by subtracting 1 or 2.
2. Top Down Memoization
In the recursion approach, we can see that, there are optimal overlapping sub problems. I.e we are calculating the same solution multiple times.
We can reduce the calculation by using Memoization. We take the temp DP array and store the computed result in the DP array. Once we get the similar value to compute, we check the DP array and take the result.
3. Bottom Up Tabular Method
Here we start from the bottom, and we move up wards towards the answer.
Here we start from 0, 1, 2, 3, 4,… steps
So we need to see, if I have to climb 0 steps in how many unique ways can I climb? 0 ways.
For 1 step, there is only 1 unique way.
For 2 steps, there are 2 unique ways.
Like this we fill our table, with number of unique ways that we can climb the steps and return the result.
Solution in C++ language:
#include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <queue> #include <vector> #include <unordered_set> #include <list> using namespace std; int calculate_ways_recursion(int n) { if(n==1) return 1; if(n==2) return 2; return calculate_ways_recursion(n-1)+calculate_ways_recursion(n-2); } int calculate_ways_top_down(int n) { int dp[n+1]; for(int i=0;i<=n;i++) dp[i]=0; //base case dp[1]=1; if(n>=2) dp[2]=2; for(int i=3;i<=n;i++){ dp[i] = dp[i-1]+dp[i-2]; } return dp[n]; } int table[46]={0}; int calculate_ways_bottom_up(int n) { if(n==1) { table[n]=1; return 1; } if(n==2) { table[n]=2; return 2; } else if(table[n]!=0) return table[n]; table[n] = calculate_ways_bottom_up(n-1)+calculate_ways_bottom_up(n-2); return table[n]; } int main(int argc, char const *argv[]) { cout<<"The number of ways the baby can climb using recursion "<< calculate_ways_recursion(4)<<endl; cout<<"The number of ways the baby can climb using top down "<< calculate_ways_top_down(4)<<endl; cout<<"The number of ways the baby can climb using bottom up "<< calculate_ways_bottom_up(4)<<endl; return 0; }
Output:
The number of ways the baby can climb using recursion 5 The number of ways the baby can climb using top down 5 The number of ways the baby can climb using bottom up 5