DP (1) - Count number of ways to cover a distance

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

Input: n = 4

Output: 7

Explantion:

Below are the four ways

 1 step + 1 step + 1 step + 1 step

 1 step + 2 step + 1 step

 2 step + 1 step + 1 step 

 1 step + 1 step + 2 step

 2 step + 2 step

 3 step + 1 step

 1 step + 3 step

// C++ program to count number of ways in DP  to cover a distance with 1, 2 and 3 steps 
#include<iostream> 
using namespace std; 
int main()
{ 
    int n;
    std::cin>>n;
    int count[n+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 from bottom to up manner 
    for (int i=3; i<=n; i++) 
       count[i] = count[i-1] + count[i-2] + count[i-3]; 
  
    std::cout<<count[n]; 
}