Tutorialspoint.dev

Count number of ways to cover a distance

Given a distance ‘dist, count total number of ways to cover the distance with 1, 2 and 3 steps.

Examples :

Input:  n = 3
Output: 4
Below are the four ways
 1 step + 1 step + 1 step
 1 step + 2 step
 2 step + 1 step
 3 step

Input:  n = 4
Output: 7

C++

// A naive recursive C++ program to count number of ways to cover
// a distance with 1, 2 and 3 steps
#include<iostream>
using namespace std;
  
// Returns count of ways to cover 'dist'
int printCountRec(int dist)
{
    // Base cases
    if (dist<0)      return 0;
    if (dist==0)  return 1;
  
    // Recur for all previous 3 and add the results
    return printCountRec(dist-1) +
           printCountRec(dist-2) +
           printCountRec(dist-3);
}
  
// driver program
int main()
{
    int dist = 4;
    cout << printCountRec(dist);
    return 0;
}

Java

// A naive recursive Java program to count number
// of ways to cover a distance with 1, 2 and 3 steps
import java.io.*;
  
class GFG 
{
    // Function returns count of ways to cover 'dist'
    static int printCountRec(int dist)
    {
        // Base cases
        if (dist<0)    
            return 0;
        if (dist==0)    
            return 1;
   
        // Recur for all previous 3 and add the results
        return printCountRec(dist-1) + 
               printCountRec(dist-2) +
               printCountRec(dist-3);
    }
      
    // driver program
    public static void main (String[] args) 
    {
        int dist = 4;
        System.out.println(printCountRec(dist));
    }
}
  
// This code is contributed by Pramod Kumar

Python3

# A naive recursive Python3 program 
# to count number of ways to cover
# a distance with 1, 2 and 3 steps
  
# Returns count of ways to 
# cover 'dist'
def printCountRec(dist):
      
    # Base cases
    if dist < 0:
        return 0
          
    if dist == 0:
        return 1
  
    # Recur for all previous 3 and       
   # add the results
    return (printCountRec(dist-1) +
            printCountRec(dist-2) +
            printCountRec(dist-3))
  
# Driver code
dist = 4
print(printCountRec(dist))
  
# This code is contributed by Anant Agarwal.

C#

// A naive recursive C# program to 
// count number of ways to cover a
// distance with 1, 2 and 3 steps
using System;
  
class GFG {
      
    // Function returns count of 
    // ways to cover 'dist'
    static int printCountRec(int dist)
    {
        // Base cases
        if (dist < 0) 
            return 0;
        if (dist == 0) 
            return 1;
  
        // Recur for all previous 3 
        // and add the results
        return printCountRec(dist - 1) + 
               printCountRec(dist - 2) +
               printCountRec(dist - 3);
    }
      
    // Driver Code
    public static void Main () 
    {
        int dist = 4;
        Console.WriteLine(printCountRec(dist));
    }
}
  
// This code is contributed by Sam007.

PHP

<?php
// A naive recursive PHP program to
// count number of ways to cover
// a distance with 1, 2 and 3 steps
  
// Returns count of ways to cover 'dist'
function printCountRec( $dist)
{
      
    // Base cases
    if ($dist<0) return 0;
    if ($dist==0) return 1;
  
    // Recur for all previous 3 
    // and add the results
    return printCountRec($dist - 1) +
           printCountRec($dist - 2) +
           printCountRec($dist - 3);
}
  
    // Driver Code
    $dist = 4;
    echo printCountRec($dist);
  
// This code is contributed by anuj_67.
?>

Output:

7

The time complexity of above solution is exponential, a close upper bound is O(3n). If we draw the complete recursion tree, we can observer that many subproblems are solved again and again. For example, when we start from n = 6, we can reach 4 by subtracting one 2 times and by subtracting 2 one times. So the subproblem for 4 is called twice.
Since same suproblems are called again, this problem has Overlapping Subprolems property. So min square sum problem has both properties (see this and this) of a dynamic programming problem. Like other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be avoided by constructing a temporary array count[] in bottom up manner.

Below is the implementation of above idea :

C++

// A Dynamic Programming based C++ program to count number of ways
// to cover a distance with 1, 2 and 3 steps
#include<iostream>
using namespace std;
  
int printCountDP(int dist)
{
    int count[dist+1];
  
    // Initialize base values. There is one way to cover 0 and 1
    // distances and two ways to cover 2 distance
    count[0]  = 1,  count[1] = 1,  count[2] = 2;
  
    // Fill the count array in bottom up manner
    for (int i=3; i<=dist; i++)
       count[i] = count[i-1] + count[i-2] + count[i-3];
  
    return count[dist];
}
  
// driver program
int main()
{
    int dist = 4;
    cout << printCountDP(dist);
    return 0;
}

Java

// A Dynamic Programming based Java program 
// to count number of ways to cover a distance 
// with 1, 2 and 3 steps
import java.io.*;
  
class GFG 
{
    // Function returns count of ways to cover 'dist'
    static int printCountDP(int dist)
    {
        int[] count = new int[dist+1];
   
        // Initialize base values. There is one way to 
        // cover 0 and 1 distances and two ways to 
        // cover 2 distance
        count[0] = 1;
        count[1] = 1;
        count[2] = 2;
   
        // Fill the count array in bottom up manner
        for (int i=3; i<=dist; i++)
            count[i] = count[i-1] + count[i-2] + count[i-3];
   
        return count[dist];
    }
      
    // driver program
    public static void main (String[] args) 
    {
        int dist = 4;
        System.out.println(printCountDP(dist));
    }
}
  
// This code is contributed by Pramod Kumar

Python3

# A Dynamic Programming based on Python3
# program to count number of ways to 
# cover a distance with 1, 2 and 3 steps
  
def printCountDP(dist):
    count = [0] * (dist + 1)
      
    # Initialize base values. There is
    # one way to cover 0 and 1 distances
    # and two ways to cover 2 distance
    count[0] = 1
    count[1] = 1
    count[2] = 2
      
    # Fill the count array in bottom
    # up manner
    for i in range(3, dist + 1):
        count[i] = (count[i-1] + 
                   count[i-2] + count[i-3])
          
    return count[dist];
  
# driver program
dist = 4;
print( printCountDP(dist))
  
# This code is contributed by Sam007.

C#

// A Dynamic Programming based C# program 
// to count number of ways to cover a distance 
// with 1, 2 and 3 steps
using System;
  
class GFG {
      
    // Function returns count of ways 
    // to cover 'dist'
    static int printCountDP(int dist)
    {
        int[] count = new int[dist + 1];
  
        // Initialize base values. There is one
        // way to cover 0 and 1 distances 
        // and two ways to cover 2 distance 
        count[0] = 1;
        count[1] = 1;
        count[2] = 2;
  
        // Fill the count array 
        // in bottom up manner
        for (int i = 3; i <= dist; i++)
            count[i] = count[i - 1] + 
                       count[i - 2] + 
                       count[i - 3];
  
        return count[dist];
    }
      
    // Driver Code
    public static void Main () 
    {
        int dist = 4;
        Console.WriteLine(printCountDP(dist));
    }
}
  
// This code is contributed by Sam007.

PHP

<?php
// A Dynamic Programming based PHP program
// to count number of ways to cover a 
// distance with 1, 2 and 3 steps
  
function printCountDP( $dist)
{
    $count = array();
  
    // Initialize base values. There is
    // one way to cover 0 and 1 distances
    // and two ways to cover 2 distance
    $count[0] = 1; $count[1] = 1; 
    $count[2] = 2;
  
    // Fill the count array 
    // in bottom up manner
    for ( $i = 3; $i <= $dist; $i++)
    $count[$i] = $count[$i - 1] + 
                 $count[$i - 2] + 
                 $count[$i - 3];
  
    return $count[$dist];
}
  
// Driver Code
$dist = 4;
echo printCountDP($dist);
  
// This code is contributed by anuj_67.
?>

Output :

7


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter