Encuentre el número mínimo de pasos para llegar al final de String

Dada una string binaria str de longitud N y un entero K , la tarea es encontrar el número mínimo de pasos necesarios para pasar de str[0] a str[N – 1] con los siguientes movimientos: 
 

1. A partir de un índice i , los únicos movimientos válidos son i + 1 , i + 2 e i + K
2. Un índice i solo puede ser visitado si str[i] = ‘1’

Ejemplos: 
 

Entrada: str = “101000011”, K = 5 
Salida: 3 
str[0] -> str[2] -> str[7] -> str[8]
Entrada: str = “1100000100111”, K = 6 
Salida: – 1 
No hay camino posible.
Entrada: str = “10101010101111010101”, K = 4 
Salida: 6 
 

Enfoque: La idea es usar programación dinámica para resolver el problema. 
 

• Se da que para cualquier índice i , es posible pasar a un índice i+1, i+2 o i+K.
• Una de las tres posibilidades dará el resultado requerido que es el número mínimo de pasos para llegar al final.
• Por lo tanto, la array dp[] se crea y se llena de forma ascendente.

A continuación se muestra la implementación del enfoque anterior: 
 

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

// Java implementation of the approach
class GFG
{
     
    final static int INT_MAX = Integer.MAX_VALUE ;
     
    // Function to return the minimum number
    // of steps to reach the end
    static int minSteps(String str, int n, int k)
    {
     
        // If the end can't be reached
        if (str.charAt(n - 1) == '0')
            return -1;
     
        // Already at the end
        if (n == 1)
            return 0;
     
        // If the length is 2 or 3 then the end
        // can be reached in a single step
        if (n < 4)
            return 1;
     
        // For the other cases, solve the problem
        // using dynamic programming
        int dp[] = new int[n];
     
        // It requires no move from the
        // end to reach the end
        dp[n - 1] = 0;
     
        // From the 2nd last and the 3rd last
        // index, only a single move is required
        dp[n - 2] = 1;
        dp[n - 3] = 1;
     
        // Update the answer for every index
        for (int i = n - 4; i >= 0; i--)
        {
     
            // If the current index is not reachable
            if (str.charAt(i) == '0')
                continue;
     
            // To store the minimum steps required
            // from the current index
            int steps =INT_MAX ;
     
            // If it is a valiINT_MAXd move then update
            // the minimum steps required
            if (i + k < n && str.charAt(i + k) == '1')
                steps = Math.min(steps, dp[i + k]);
     
            if (str.charAt(i + 1) == '1')
                steps = Math.min(steps, dp[i + 1]);
     
            if (str.charAt(i + 2) == '1')
                steps = Math.min(steps, dp[i + 2]);
     
            // Update the minimum steps required starting
            // from the current index
            dp[i] = (steps == INT_MAX) ? steps : 1 + steps;
        }
     
        // Cannot reach the end starting from str[0]
        if (dp[0] == INT_MAX)
            return -1;
     
        // Return the minimum steps required
        return dp[0];
    }
     
    // Driver code
    public static void main(String[] args)
    {
        String str = "101000011";
        int n = str.length();
        int k = 5;
     
        System.out.println(minSteps(str, n, k));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
import sys
 
INT_MAX = sys.maxsize;
 
# Function to return the minimum number
# of steps to reach the end
def minSteps(string , n, k) :
     
    # If the end can't be reached
    if (string[n - 1] == '0') :
        return -1;
 
    # Already at the end
    if (n == 1) :
        return 0;
 
    # If the length is 2 or 3 then the end
    # can be reached in a single step
    if (n < 4) :
        return 1;
 
    # For the other cases, solve the problem
    # using dynamic programming
    dp = [0] * n;
 
    # It requires no move from the
    # end to reach the end
    dp[n - 1] = 0;
 
    # From the 2nd last and the 3rd last
    # index, only a single move is required
    dp[n - 2] = 1;
    dp[n - 3] = 1;
 
    # Update the answer for every index
    for i in range(n - 4, -1, -1) :
         
        # If the current index is not reachable
        if (string[i] == '0') :
            continue;
 
        # To store the minimum steps required
        # from the current index
        steps = INT_MAX;
 
        # If it is a valid move then update
        # the minimum steps required
        if (i + k < n and string[i + k] == '1') :
            steps = min(steps, dp[i + k]);
 
        if (string[i + 1] == '1') :
            steps = min(steps, dp[i + 1]);
 
        if (string[i + 2] == '1') :
            steps = min(steps, dp[i + 2]);
 
        # Update the minimum steps required starting
        # from the current index
        dp[i] = steps if (steps == INT_MAX) else (1 + steps);
     
    # Cannot reach the end starting from str[0]
    if (dp[0] == INT_MAX) :
        return -1;
 
    # Return the minimum steps required
    return dp[0];
 
# Driver code
if __name__ == "__main__" :
 
    string = "101000011";
    n = len(string);
    k = 5;
 
    print(minSteps(string, n, k));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
     
    static int INT_MAX = int.MaxValue ;
     
    // Function to return the minimum number
    // of steps to reach the end
    static int minSteps(string str, int n, int k)
    {
     
        // If the end can't be reached
        if (str[n - 1] == '0')
            return -1;
     
        // Already at the end
        if (n == 1)
            return 0;
     
        // If the length is 2 or 3 then the end
        // can be reached in a single step
        if (n < 4)
            return 1;
     
        // For the other cases, solve the problem
        // using dynamic programming
        int []dp = new int[n];
     
        // It requires no move from the
        // end to reach the end
        dp[n - 1] = 0;
     
        // From the 2nd last and the 3rd last
        // index, only a single move is required
        dp[n - 2] = 1;
        dp[n - 3] = 1;
     
        // Update the answer for every index
        for (int i = n - 4; i >= 0; i--)
        {
     
            // If the current index is not reachable
            if (str[i] == '0')
                continue;
     
            // To store the minimum steps required
            // from the current index
            int steps = INT_MAX ;
     
            // If it is a valiINT_MAXd move then update
            // the minimum steps required
            if (i + k < n && str[i + k] == '1')
                steps = Math.Min(steps, dp[i + k]);
     
            if (str[i + 1] == '1')
                steps = Math.Min(steps, dp[i + 1]);
     
            if (str[i + 2] == '1')
                steps = Math.Min(steps, dp[i + 2]);
     
            // Update the minimum steps required starting
            // from the current index
            dp[i] = (steps == INT_MAX) ? steps : 1 + steps;
        }
     
        // Cannot reach the end starting from str[0]
        if (dp[0] == INT_MAX)
            return -1;
     
        // Return the minimum steps required
        return dp[0];
    }
     
    // Driver code
    public static void Main()
    {
        string str = "101000011";
        int n = str.Length;
        int k = 5;
     
        Console.WriteLine(minSteps(str, n, k));
    }
}
 
// This code is contributed by AnkitRai01

<script>
  
// Javascript implementation of the approach
 
// Function to return the minimum number
// of steps to reach the end
function minSteps(str, n, k)
{
 
    // If the end can't be reached
    if (str[n - 1] == '0')
        return -1;
 
    // Already at the end
    if (n == 1)
        return 0;
 
    // If the length is 2 or 3 then the end
    // can be reached in a single step
    if (n < 4)
        return 1;
 
    // For the other cases, solve the problem
    // using dynamic programming
    var dp = Array(n);
 
    // It requires no move from the
    // end to reach the end
    dp[n - 1] = 0;
 
    // From the 2nd last and the 3rd last
    // index, only a single move is required
    dp[n - 2] = 1;
    dp[n - 3] = 1;
 
    // Update the answer for every index
    for (var i = n - 4; i >= 0; i--) {
 
        // If the current index is not reachable
        if (str[i] == '0')
            continue;
 
        // To store the minimum steps required
        // from the current index
        var steps = 1000000000;
 
        // If it is a valid move then update
        // the minimum steps required
        if (i + k < n && str[i + k] == '1')
            steps = Math.min(steps, dp[i + k]);
 
        if (str[i + 1] == '1')
            steps = Math.min(steps, dp[i + 1]);
 
        if (str[i + 2] == '1')
            steps = Math.min(steps, dp[i + 2]);
 
        // Update the minimum steps required starting
        // from the current index
        dp[i] = (steps == 1000000000) ? steps : 1 + steps;
    }
 
    // Cannot reach the end starting from str[0]
    if (dp[0] == 1000000000)
        return -1;
 
    // Return the minimum steps required
    return dp[0];
}
 
// Driver code
var str = "101000011";
var n = str.length;
var k = 5;
document.write( minSteps(str, n, k));
 
// This code is contributed by famously.
</script>

3

Complejidad de tiempo: O(N) donde N es la longitud de la string.