Expected number of moves to reach the end of a board | Dynamic programming | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define maxSize  50 NEW_LINE using namespace std ; double dp [ maxSize ] ; int v [ maxSize ] ; double expectedSteps ( int x ) { if ( x == 0 ) return 0 ; if ( x <= 5 ) return 6 ; if ( v [ x ] ) 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 ] ; } int main ( ) { int n = 10 ; cout << expectedSteps ( n - 1 ) ; return 0 ; }