Minimize the number of steps required to reach the end of the array | C ++ 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
#include <bits/stdc++.h> NEW_LINE #define maxLen  10 NEW_LINE #define maskLen  130 NEW_LINE using namespace std ; int dp [ maxLen ] [ maskLen ] ; bool v [ maxLen ] [ maskLen ] ; int minSteps ( int arr [ ] , int i , int mask , int n ) { if ( i == n - 1 ) return 0 ; if ( i > n - 1 i < 0 ) return 9999999 ; if ( ( mask >> i ) & 1 ) return 9999999 ; if ( v [ i ] [ mask ] ) return dp [ i ] [ mask ] ; v [ i ] [ mask ] = 1 ; dp [ i ] [ mask ] = 1 + min ( minSteps ( arr , i - arr [ i ] , ( mask | ( 1 << i ) ) , n ) , minSteps ( arr , i + arr [ i ] , ( mask | ( 1 << i ) ) , n ) ) ; return dp [ i ] [ mask ] ; } int main ( ) { int arr [ ] = { 1 , 2 , 2 , 2 , 1 , 1 } ; int n = sizeof ( arr ) / sizeof ( int ) ; int ans = minSteps ( arr , 0 , 0 , n ) ; if ( ans >= 9999999 ) cout << -1 ; else cout << ans ; }