Minimize the number of steps required to reach the end of the array | Python3 implementation of the above approach ; variable to store states of dp ; variable to check if a given state has been solved ; Function to find the minimum number of steps required to reach the end of the array ; base case ; to check if a state has been solved ; required recurrence relation ; returning the value ; Driver code
maxLen = 10 NEW_LINE maskLen = 130 NEW_LINE dp = [ [ 0 for i in range ( maskLen ) ] for i in range ( maxLen ) ] NEW_LINE v = [ [ False for i in range ( maskLen ) ] for i in range ( maxLen ) ] NEW_LINE def minSteps ( arr , i , mask , n ) : NEW_LINE INDENT if ( i == n - 1 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( i > n - 1 or i < 0 ) : NEW_LINE INDENT return 9999999 NEW_LINE DEDENT if ( ( mask >> i ) & 1 ) : NEW_LINE INDENT return 9999999 NEW_LINE DEDENT if ( v [ i ] [ mask ] == True ) : NEW_LINE INDENT return dp [ i ] [ mask ] NEW_LINE DEDENT v [ i ] [ mask ] = True NEW_LINE dp [ i ] [ mask ] = 1 + min ( minSteps ( arr , i - arr [ i ] , ( mask | ( 1 << i ) ) , n ) , minSteps ( arr , i + arr [ i ] , ( mask | ( 1 << i ) ) , n ) ) NEW_LINE return dp [ i ] [ mask ] NEW_LINE DEDENT arr = [ 1 , 2 , 2 , 2 , 1 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE ans = minSteps ( arr , 0 , 0 , n ) NEW_LINE if ( ans >= 9999999 ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( ans ) NEW_LINE DEDENT