Count number of ways to cover a distance | A Dynamic Programming based C ++ program to count number of ways ; Create the array of size 3. ; Initialize the bases cases ; Run a loop from 3 to n Bottom up approach to fill the array ; driver program
def prCountDP ( dist ) : NEW_LINE INDENT ways = [ 0 ] * 3 NEW_LINE n = dist NEW_LINE ways [ 0 ] = 1 NEW_LINE ways [ 1 ] = 1 NEW_LINE ways [ 2 ] = 2 NEW_LINE for i in range ( 3 , n + 1 ) : NEW_LINE INDENT ways [ i % 3 ] = ways [ ( i - 1 ) % 3 ] + ways [ ( i - 2 ) % 3 ] + ways [ ( i - 3 ) % 3 ] NEW_LINE DEDENT return ways [ n % 3 ] NEW_LINE DEDENT dist = 4 NEW_LINE print ( prCountDP ( dist ) ) NEW_LINE