Count number of ways to cover a distance | 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
def printCountDP ( dist ) : NEW_LINE INDENT count = [ 0 ] * ( dist + 1 ) NEW_LINE count [ 0 ] = 1 NEW_LINE if dist >= 1 : NEW_LINE INDENT count [ 1 ] = 1 NEW_LINE DEDENT if dist >= 2 : NEW_LINE INDENT count [ 2 ] = 2 NEW_LINE DEDENT for i in range ( 3 , dist + 1 ) : NEW_LINE INDENT count [ i ] = ( count [ i - 1 ] + count [ i - 2 ] + count [ i - 3 ] ) NEW_LINE DEDENT return count [ dist ] ; NEW_LINE DEDENT dist = 4 ; NEW_LINE print ( printCountDP ( dist ) ) NEW_LINE