Expected number of moves to reach the end of a board | Dynamic programming | Java 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
class GFG { static int maxSize = 50 ; static double dp [ ] = new double [ maxSize ] ; static int v [ ] = new int [ maxSize ] ; static double expectedSteps ( int x ) { if ( x == 0 ) return 0 ; if ( x <= 5 ) return 6 ; if ( v [ x ] == 1 ) return dp [ x ] ; v [ x ] = 1 ; dp [ x ] = 1 + ( expectedSteps ( x - 1 ) + expectedSteps ( x - 2 ) + expectedSteps ( x - 3 ) + expectedSteps ( x - 4 ) + expectedSteps ( x - 5 ) + expectedSteps ( x - 6 ) ) / 6 ; return dp [ x ] ; } public static void main ( String [ ] args ) { int n = 10 ; System . out . println ( expectedSteps ( n - 1 ) ) ; } }