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