Find minimum number of steps to reach the end of String | Python3 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
import sys NEW_LINE INT_MAX = sys . maxsize ; NEW_LINE def minSteps ( string , n , k ) : NEW_LINE INDENT if ( string [ n - 1 ] == '0' ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT if ( n == 1 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if ( n < 4 ) : NEW_LINE INDENT return 1 ; NEW_LINE DEDENT dp = [ 0 ] * n ; NEW_LINE dp [ n - 1 ] = 0 ; NEW_LINE dp [ n - 2 ] = 1 ; NEW_LINE dp [ n - 3 ] = 1 ; NEW_LINE for i in range ( n - 4 , - 1 , - 1 ) : NEW_LINE INDENT if ( string [ i ] == '0' ) : NEW_LINE INDENT continue ; NEW_LINE DEDENT steps = INT_MAX ; NEW_LINE if ( i + k < n and string [ i + k ] == '1' ) : NEW_LINE INDENT steps = min ( steps , dp [ i + k ] ) ; NEW_LINE DEDENT if ( string [ i + 1 ] == '1' ) : NEW_LINE INDENT steps = min ( steps , dp [ i + 1 ] ) ; NEW_LINE DEDENT if ( string [ i + 2 ] == '1' ) : NEW_LINE INDENT steps = min ( steps , dp [ i + 2 ] ) ; NEW_LINE DEDENT dp [ i ] = steps if ( steps == INT_MAX ) else ( 1 + steps ) ; NEW_LINE DEDENT if ( dp [ 0 ] == INT_MAX ) : NEW_LINE INDENT return - 1 ; NEW_LINE DEDENT return dp [ 0 ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = "101000011" ; NEW_LINE n = len ( string ) ; NEW_LINE k = 5 ; NEW_LINE print ( minSteps ( string , n , k ) ) ; NEW_LINE DEDENT