Tutorialspoint.dev

Count ways to reach the nth stair using step 1, 2 or 3

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how many possible ways the child can run up the stairs.

There are two methods to solve this problem
1. Recursive Method
2. Dynamic Programming

Examples :



Input : 4
Output : 7

Input : 3
Output : 4

1. Recursive Method
How Code is Working :
Suppose you have n stairs then you can hop either 1 step, 2 step, 3 step.
1. If you hop 1 step then remaining stairs = n-1
2. If you hop 2 step then remaining stairs = n-2
3. If you hop 3 step then remaining stairs = n-3

If you hop 1 step then again you can hop 1 step, 2 step, 3 step until n equals 0.
Repeat this process and count total number of ways to reach at nth stair using step 1, 2, 3.

C++

// C++ Program to find n-th stair using step size
// 1 or 2 or 3.
#include <iostream>
using namespace std;
  
class GFG
{
      
// Returns count of ways to reach n-th stair
// using 1 or 2 or 3 steps.
public :int findStep(int n)
{
    if (n == 1 || n == 0) 
        return 1;
    else if (n == 2) 
        return 2;
      
    else
        return findStep(n - 3) + 
            findStep(n - 2) +
            findStep(n - 1); 
}
};
  
// Driver code
int main()
{
    GFG g ;
    int n = 4;
    cout << g.findStep(n);
    return 0;
}
  
// This code is contributed by SoM15242

C

// Program to find n-th stair using step size
// 1 or 2 or 3.
#include <stdio.h>
  
// Returns count of ways to reach n-th stair
// using 1 or 2 or 3 steps.
int findStep(int n)
{
    if (n == 1 || n == 0) 
        return 1;
    else if (n == 2) 
        return 2;
      
    else 
        return findStep(n - 3) + 
               findStep(n - 2) +
               findStep(n - 1);    
}
  
// Driver code
int main()
{
    int n = 4;
    printf("%d ", findStep(n));
    return 0;
}

Java

// Program to find n-th stair
// using step size 1 or 2 or 3.
import java.util.*;
import java.lang.*;
  
public class GfG{
      
    // Returns count of ways to reach
    // n-th stair using 1 or 2 or 3 steps.
    public static int findStep(int n)
    {
        if (n == 1 || n == 0
            return 1;
        else if (n == 2
            return 2;
       
        else
            return findStep(n - 3) + 
                   findStep(n - 2) +
                   findStep(n - 1);    
    }
      
    // Driver function
    public static void main(String argc[]){
        int n = 4;
        System.out.println(findStep(n));
    }
}
  
/* This code is contributed by Sagar Shukla */

Python

# Python program to find n-th stair  
# using step size 1 or 2 or 3.
  
# Returns count of ways to reach n-th 
# stair using 1 or 2 or 3 steps.
def findStep( n) :
    if (n == 1 or n == 0) :
        return 1
    elif (n == 2) :
        return 2
      
    else :
        return findStep(n - 3) + findStep(n - 2) + findStep(n - 1
  
  
# Driver code
n = 4
print(findStep(n))
  
#This code is contributed by Nikita Tiwari.

C#

// Program to find n-th stair
// using step size 1 or 2 or 3.
using System;
  
public class GfG{
      
    // Returns count of ways to reach
    // n-th stair using 1 or 2 or 3 steps.
    public static int findStep(int n)
    {
        if (n == 1 || n == 0) 
            return 1;
        else if (n == 2) 
            return 2;
      
        else
            return findStep(n - 3) + 
                   findStep(n - 2) +
                   findStep(n - 1); 
    }
      
    // Driver function
    public static void Main(){
        int n = 4;
        Console.WriteLine(findStep(n));
    }
}
  
/* This code is contributed by vt_m */

PHP

<?php
// PHP Program to find n-th stair 
// using step size 1 or 2 or 3.
  
// Returns count of ways to 
// reach n-th stair using  
// 1 or 2 or 3 steps.
function findStep($n)
{
    if ($n == 1 || $n == 0) 
        return 1;
    else if ($n == 2) 
        return 2;
      
    else
        return findStep($n - 3) + 
               findStep($n - 2) +
                findStep($n - 1); 
}
  
// Driver code
$n = 4;
echo findStep($n);
  
// This code is contributed by m_kit
?>


Output :



7

How Code is Working….

The Time Complexity of the program is Optimized using Dynamic Programming.

2. Using Dynamic Programming

C

// A C program to count number of ways to reach n't stair when
#include <stdio.h>
  
// A recursive function used by countWays
int countWays(int n)
{
    int res[n + 1];
    res[0] = 1;
    res[1] = 1;
    res[2] = 2;
    for (int i = 3; i <= n; i++) 
        res[i] = res[i-1] + res[i-2] 
                          + res[i-3];
      
    return res[n];
}
  
// Driver program to test above functions
int main()
{
    int n = 4;
    printf("%d", countWays(n));
    return 0;
}

Java

// Program to find n-th stair
// using step size 1 or 2 or 3.
import java.util.*;
import java.lang.*;
  
public class GfG {
  
    // A recursive function used by countWays
    public static int countWays(int n)
    {
        int[] res = new int[n + 1];
        res[0] = 1;
        res[1] = 1;
        res[2] = 2;
  
        for (int i = 3; i <= n; i++)
            res[i] = res[i - 1] + res[i - 2]
                                + res[i - 3];
  
        return res[n];
    }
  
    // Driver function
    public static void main(String argc[])
    {
        int n = 4;
        System.out.println(countWays(n));
    }
}
  
/* This code is contributed by Sagar Shukla */

Python

# Python program to find n-th stair  
# using step size 1 or 2 or 3.
  
# A recursive function used by countWays
def countWays(n) :
    res = [0] * (n + 1)
    res[0] = 1
    res[1] = 1
    res[2] = 2
      
    for i in range(3, n + 1) :
        res[i] = res[i - 1] + res[i - 2] + res[i - 3]
      
    return res[n]
  
# Driver code
n = 4
print(countWays(n))
  
  
# This code is contributed by Nikita Tiwari.

C#

// Program to find n-th stair
// using step size 1 or 2 or 3.
using System;
  
public class GfG {
  
    // A recursive function used by countWays
    public static int countWays(int n)
    {
        int[] res = new int[n + 1];
        res[0] = 1;
        res[1] = 1;
        res[2] = 2;
  
        for (int i = 3; i <= n; i++)
            res[i] = res[i - 1] + res[i - 2]
                                + res[i - 3];
  
        return res[n];
    }
  
    // Driver function
    public static void Main()
    {
        int n = 4;
        Console.WriteLine(countWays(n));
    }
}
  
/* This code is contributed by vt_m */

PHP

<?php
// A PHP program to count 
// number of ways to reach 
// n'th stair when
  
// A recursive function
// used by countWays
function countWays($n)
{
    $res[0] = 1;
    $res[1] = 1;
    $res[2] = 2;
    for ($i = 3; $i <= $n; $i++) 
        $res[$i] = $res[$i - 1] + 
                   $res[$i - 2] + 
                   $res[$i - 3];
      
    return $res[$n];
}
  
// Driver Code
$n = 4;
echo countWays($n);
  
// This code is contributed by ajit
?>


Output :

7

Output Explanation :
1 -> 1 -> 1 -> 1
1 -> 1 -> 2
1 -> 2 -> 1
1 -> 3
2 -> 1 -> 1
2 -> 2
3 -> 1

So Total ways: 7

Other Related Articles
https://tutorialspoint.dev/slugresolver/count-ways-reach-nth-stair/

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter