Find minimum number of steps to reach the end of String | C ++ implementation of the approach ; Function to return the minimum number of steps to reach the end ; If the end can 't be reached ; Already at the end ; If the length is 2 or 3 then the end can be reached in a single step ; For the other cases , solve the problem using dynamic programming ; It requires no move from the end to reach the end ; From the 2 nd last and the 3 rd last index , only a single move is required ; Update the answer for every index ; If the current index is not reachable ; To store the minimum steps required from the current index ; If it is a valid move then update the minimum steps required ; Update the minimum steps required starting from the current index ; Cannot reach the end starting from str [ 0 ] ; Return the minimum steps required ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minSteps ( string str , int n , int k ) { if ( str [ n - 1 ] == '0' ) return -1 ; if ( n == 1 ) return 0 ; if ( n < 4 ) return 1 ; int dp [ n ] ; dp [ n - 1 ] = 0 ; dp [ n - 2 ] = 1 ; dp [ n - 3 ] = 1 ; for ( int i = n - 4 ; i >= 0 ; i -- ) { if ( str [ i ] == '0' ) continue ; int steps = INT_MAX ; if ( i + k < n && str [ i + k ] == '1' ) steps = min ( steps , dp [ i + k ] ) ; if ( str [ i + 1 ] == '1' ) steps = min ( steps , dp [ i + 1 ] ) ; if ( str [ i + 2 ] == '1' ) steps = min ( steps , dp [ i + 2 ] ) ; dp [ i ] = ( steps == INT_MAX ) ? steps : 1 + steps ; } if ( dp [ 0 ] == INT_MAX ) return -1 ; return dp [ 0 ] ; } int main ( ) { string str = "101000011" ; int n = str . length ( ) ; int k = 5 ; cout << minSteps ( str , n , k ) ; return 0 ; }