Expected number of moves to reach the end of a board | Dynamic programming | Python3 implementation of the approach ; To store the states of dp ; To determine whether a state has been solved before ; Function to return the count ; Base cases ; If a state has been solved before it won 't be evaluated again ; Recurrence relation ; Driver code
maxSize = 50 NEW_LINE dp = [ 0 ] * maxSize NEW_LINE v = [ 0 ] * maxSize NEW_LINE def expectedSteps ( x ) : NEW_LINE INDENT if ( x == 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( x <= 5 ) : NEW_LINE INDENT return 6 NEW_LINE DEDENT if ( v [ x ] ) : NEW_LINE INDENT return dp [ x ] NEW_LINE DEDENT v [ x ] = 1 NEW_LINE dp [ x ] = 1 + ( expectedSteps ( x - 1 ) + expectedSteps ( x - 2 ) + expectedSteps ( x - 3 ) + expectedSteps ( x - 4 ) + expectedSteps ( x - 5 ) + expectedSteps ( x - 6 ) ) / 6 NEW_LINE return dp [ x ] NEW_LINE DEDENT n = 10 NEW_LINE print ( round ( expectedSteps ( n - 1 ) , 5 ) ) NEW_LINE