text: Check if end of given Binary string can be reached by choosing jump value in between given range | C ++ program for the above approach ; Function to check if it is possible to reach the end of the binary string using the given jumps ; Stores the DP states ; Initial state ; Stores count of indices from which it is possible to reach index i ; Traverse the given string ; Update the values of pre accordingly ; If the jump size is out of the range [ L , R ] ; Return answer ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; bool canReach ( string s , int L , int R ) { vector < int > dp ( s . length ( ) ) ; dp [ 0 ] = 1 ; int pre = 0 ; for ( int i = 1 ; i < s . length ( ) ; i ++ ) { if ( i >= L ) { pre += dp [ i - L ] ; } if ( i > R ) { pre -= dp [ i - R - 1 ] ; } dp [ i ] = ( pre > 0 ) and ( s [ i ] == '0' ) ; } return dp [ s . length ( ) - 1 ] ; } int main ( ) { string S = "01101110" ; int L = 2 , R = 3 ; cout << ( canReach ( S , L , R ) ? " Yes " : " No " ) ; return 0 ; }