A monkey is standing below at a staircase having N steps. Considering it can take a leap of 1 to N steps at a time, calculate how many ways it can reach the top of the staircase?
Input : 2
Output : 2
It can either take (1, 1) or (2) to
reach the top. So, total 2 ways
Input : 3
Output : 4
Possibilities : (1, 1, 1), (1, 2), (2, 1),
(3). So, total 4 ways
There are 3 different ways to think of the problem.
- In all possible solutions, a step is either stepped on by the monkey or can be skipped. So using the fundamental counting principle, the first step has 2 ways to take part, and for each of these, 2nd step also has 2 ways, and so on. but the last step always has to be stepped on.
2 x 2 x 2 x .... x 2(N-1 th step) x 1(Nth step)
= 2(N-1) different ways.
- Let’s define a function F(n) for the use case. F(n) denotes all possible way to reach from bottom to top of a staircase having N steps, where min leap is 1 step and max leap is N step. Now, for the monkey, the first move it can make is possible in N different ways ( 1 step, 2 steps, 3 steps .. N steps). If it takes the first leap as 1 step, it will be left with N-1 more steps to conquer, which can be achieved in F(N-1) ways. And if it takes the first leap as 2 steps, it will have N-2 steps more to cover, which can be achieved in F(N-2) ways. Putting together,
F(N) = F(N-1) + F(N-2) + F(N-3) + ... +
F(2) + F(1) + F(0)
Now,
F(0) = 1
F(1) = 1
F(2) = 2
F(3) = 4
Hence,
F(N) = 1 + 1 + 2 + 4 + ... + F(n-1)
= 1 + 2^0 + 2^1 + 2^2 + ... + 2^(n-2)
= 1 + [2^(n-1) - 1]
C++
#include <iostream>
int calculateLeaps( int n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
int leaps = 0;
for ( int i = 0; i < n; i++)
leaps += calculateLeaps(i);
return leaps;
}
}
int main()
{
int calculateLeaps( int );
std::cout << calculateLeaps(4) << std::endl;
return 0;
}
|
Java
class GFG {
static int calculateLeaps( int n)
{
if (n == 0 || n == 1 ) {
return 1 ;
}
else {
int leaps = 0 ;
for ( int i = 0 ; i < n; i++)
leaps += calculateLeaps(i);
return leaps;
}
}
public static void main(String[] args)
{
System.out.println(calculateLeaps( 4 ));
}
}
|
Python3
def calculateLeaps(n):
if n = = 0 or n = = 1 :
return 1 ;
else :
leaps = 0 ;
for i in range ( 0 ,n):
leaps = leaps + calculateLeaps(i);
return leaps;
print (calculateLeaps( 4 ));
|
C#
using System;
class GFG {
static int calculateLeaps( int n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
int leaps = 0;
for ( int i = 0; i < n; i++)
leaps += calculateLeaps(i);
return leaps;
}
}
public static void Main()
{
Console.WriteLine(calculateLeaps(4));
}
}
|
PHP
<?php
function calculateLeaps( $n )
{
if ( $n == 0 || $n == 1)
{
return 1;
}
else
{
$leaps = 0;
for ( $i = 0; $i < $n ; $i ++)
$leaps += calculateLeaps( $i );
return $leaps ;
}
}
echo calculateLeaps(4), "\n" ;
?>
|
Javascript
<script>
function calculateLeaps(n)
{
if (n == 0 || n == 1) {
return 1;
}
else {
let leaps = 0;
for (let i = 0; i < n; i++)
leaps += calculateLeaps(i);
return leaps;
}
}
document.write(calculateLeaps(4));
</script>
|
Auxiliary Space: O(n) due to recursive stack space
2. The above solution can be improved by using Dynamic programming (Bottom-Up Approach)
Leaps(3)
3/ 2| 1\
Leaps(0) Leaps(1) Leaps(2)
/ | \ 3/ 2| 1\
Leaps(-3) Leaps(-2) Leaps(-1) Lepas(-1) Leaps(0) Leaps(1)
C++
#include <iostream>
using namespace std;
int calculateLeaps( int n, int dp[]){
if (n == 0){
return 1 ;
} else if (n < 0){
return 0 ;
}
if (dp[n] != 0 ){
return dp[n] ;
}
int count = 0;
for ( int i = 0 ; i < n ; i++ ){
count += calculateLeaps(i, dp) ;
}
dp[n] = count ;
return count ;
}
int main() {
int n = 4 ;
int dp[n+1] = {0} ;
cout<<calculateLeaps(n,dp) ;
return 0;
}
|
Java
import java.io.*;
class GFG
{
public static int calculateLeaps( int n, int dp[])
{
if (n == 0 )
{
return 1 ;
}
else if (n < 0 )
{
return 0 ;
}
if (dp[n] != 0 )
{
return dp[n] ;
}
int count = 0 ;
for ( int i = 0 ; i < n ; i++)
{
count += calculateLeaps(i, dp);
}
dp[n] = count;
return count;
}
public static void main (String[] args)
{
int n = 4 ;
int dp[] = new int [n+ 1 ];
System.out.println(calculateLeaps(n,dp));
}
}
|
Python3
def calculateLeaps(n, dp):
if (n = = 0 ):
return 1
elif (n < 0 ):
return 0
if (dp[n] ! = 0 ):
return dp[n]
count = 0
for i in range (n):
count + = calculateLeaps(i, dp)
dp[n] = count
return count
n = 4
dp = [ 0 ] * (n + 1 )
print (calculateLeaps(n,dp))
|
C#
using System;
class GFG
{
public static int calculateLeaps( int n, int [] dp)
{
if (n == 0)
{
return 1 ;
}
else if (n < 0)
{
return 0 ;
}
if (dp[n] != 0)
{
return dp[n] ;
}
int count = 0;
for ( int i = 0 ; i < n ; i++)
{
count += calculateLeaps(i, dp);
}
dp[n] = count;
return count;
}
public static void Main ( string [] args)
{
int n = 4;
int [] dp = new int [n+1];
Console.WriteLine(calculateLeaps(n,dp));
}
}
|
Javascript
<script>
function calculateLeaps(n, dp){
if (n == 0){
return 1
} else if (n < 0){
return 0
}
if (dp[n] != 0 ){
return dp[n]
}
let count = 0
for (let i = 0 ; i < n ; i++ ){
count += calculateLeaps(i, dp)
}
dp[n] = count
return count
}
let n = 4
let dp = new Array(n+1).fill(0)
document.write(calculateLeaps(n,dp))
</script>
|
Time Complexity: O(n) // maximum different states
Auxiliary Space : O(n) + O(n) -> O(n) // auxiliary stack space + dp array size
3. Let’s break this problem into small subproblems. The monkey has to step on the last step, the first N-1 steps are optional. The monkey can step on 0 steps before reaching the top step, which is the biggest leap to the top. Or it can decide to step on only once in between, which can be achieved in n-1 ways [ (N-1)C1 ]. And so on, it can step on only 2 steps before reaching the top in (N-1)C2 ways. Putting together..
F(N) = (N-1)C0 + (N-1)C1 + (N-1)C2 + … + (N-1)C(N-2) + (N-1)C(N-1)
Which is sum of binomial coefficient.
= 2^(n-1)
C++
#include <bits/stdc++.h>
using namespace std;
int calculateLeaps( int n)
{
if (n == 0)
return 1;
return (1 << (n - 1));
}
int main()
{
int calculateLeaps( int );
std::cout << calculateLeaps(4) << std::endl;
return 0;
}
|
Java
class GFG {
static int calculateLeaps( int n)
{
if (n == 0 )
return 1 ;
return ( 1 << (n - 1 ));
}
public static void main(String[] args)
{
System.out.println(calculateLeaps( 4 ));
}
}
|
Python3
def calculateLeaps(n):
if (n = = 0 ):
return 1 ;
return ( 1 << (n - 1 ));
print (calculateLeaps( 4 ));
|
C#
using System;
class GFG {
static int calculateLeaps( int n)
{
if (n == 0)
return 1;
return (1 << (n - 1));
}
public static void Main()
{
Console.WriteLine(calculateLeaps(4));
}
}
|
PHP
<?php
function calculateLeaps( $n )
{
if ( $n == 0)
return 1;
return (1 << ( $n - 1));
}
echo calculateLeaps(4);
?>
|
Javascript
<script>
function calculateLeaps(n)
{
if (n == 0)
return 1;
return (1 << (n - 1));
}
document.write(calculateLeaps(4));
</script>
|