Compruebe si se puede alcanzar el final de la string binaria dada eligiendo el valor de salto entre el rango dado

Dados dos números enteros positivos L y R y una string binaria S de tamaño N , la tarea es verificar si el final de la string se alcanza desde el índice 0 mediante una serie de saltos de índices, digamos i tales que S[i] es Se permiten 0 saltos en el rango [L, R] . Si es posible llegar, imprima Sí . De lo contrario , imprima No.

Ejemplos:

Entrada: S = “011010”, L = 2, R = 3
Salida: Sí
Explicación: Las
siguientes son series de movimientos que tienen caracteres en esos índices como 0:
S[0](= 0) -> S[3](= 0) -> S[5](= 0) y S[5] es el final de la string S.
Por lo tanto, imprima Sí.

Entrada: S = “01101110”, L = 2, R = 3
Salida: No

Enfoque: el problema anterior se puede resolver con la ayuda de la programación dinámica , la idea es mantener una array 1D , digamos dp[] donde dp[i] almacenará la posibilidad de alcanzar la i ^-ésima posición y actualizará cada índice en consecuencia. A continuación se muestran los pasos:

• Inicialice una array, dp[] tal que dp[i] almacene si se puede acceder a algún índice i desde el índice 0 o no. Actualice el valor de dp[0] como 1 , ya que es el índice permanente actual.
• Inicializa una variable, pre como 0 , que almacena el número de índices desde los que se puede acceder al índice actual.
• Itere sobre el rango [1, N) y actualice el valor de la variable pre de la siguiente manera:
  • Si el valor de ( i >= minJump ), entonces incremente el valor de pre por dp[i – minJump] .
  • Si el valor de ( i > maxJump ), entonces disminuya el valor de pre por dp[i – maxJump – 1] .
• Si el valor de pre es positivo, entonces hay al menos 1 índice desde el cual se puede alcanzar el índice actual. Por lo tanto, actualice el valor de dp[i] = 1 , si el valor de S[i] = 0 .
• Después de completar los pasos anteriores, si el valor de dp[N – 1] es positivo, imprima Sí . De lo contrario , imprima No.

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

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

// Java program for the above approach
 
public class GFG {
     
    // Function to check if it is possible
    // to reach the end of the binary string
    // using the given jumps
    static int canReach(String s, int L, int R)
    {
       
        // Stores the DP states
        int dp[] = new int[s.length()];
         
        // Initial state
        dp[0] = 1;
     
        // Stores count of indices from which
        // it is possible to reach index i
        int pre = 0;
     
        // Traverse the given string
        for (int i = 1; i < s.length(); i++) {
     
            // Update the values of pre
            // accordingly
            if (i >= L) {
                pre += dp[i - L];
            }
     
            // If the jump size is out of
            // the range [L, R]
            if (i > R) {
                pre -= dp[i - R - 1];
            }
             
            if (pre > 0 && s.charAt(i) == '0')
                 dp[i] = 1;
            else
                dp[i] = 0;
        }
     
        // Return answer
        return dp[s.length() - 1];
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        String S = "01101110";
        int L = 2, R = 3;
     
        if (canReach(S, L, R) == 1)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by AnkThon

# python program for the above approach
 
# Function to check if it is possible
# to reach the end of the binary string
# using the given jumps
 
 
def canReach(s, L, R):
 
    # Stores the DP states
    dp = [0 for _ in range(len(s))]
 
    # Initial state
    dp[0] = 1
 
    # Stores count of indices from which
    # it is possible to reach index i
    pre = 0
 
    # Traverse the given string
    for i in range(1, len(s)):
 
        # Update the values of pre
        # accordingly
        if (i >= L):
            pre += dp[i - L]
 
        # If the jump size is out of
        # the range [L, R]
        if (i > R):
            pre -= dp[i - R - 1]
 
        dp[i] = (pre > 0) and (s[i] == '0')
 
    # Return answer
    return dp[len(s) - 1]
 
 
# Driver Code
if __name__ == "__main__":
 
    S = "01101110"
    L = 2
    R = 3
 
    if canReach(S, L, R):
        print("Yes")
    else:
        print("No")
 
    # This code is contributed by rakeshsahni

// C#  program for the above approach
using System;
public class GFG
{
 
    // Function to check if it is possible
    // to reach the end of the binary string
    // using the given jumps
    static int canReach(String s, int L, int R)
    {
 
        // Stores the DP states
        int[] dp = new int[s.Length];
 
        // Initial state
        dp[0] = 1;
 
        // Stores count of indices from which
        // it is possible to reach index i
        int pre = 0;
 
        // Traverse the given string
        for (int i = 1; i < s.Length; i++)
        {
 
            // Update the values of pre
            // accordingly
            if (i >= L)
            {
                pre += dp[i - L];
            }
 
            // If the jump size is out of
            // the range [L, R]
            if (i > R)
            {
                pre -= dp[i - R - 1];
            }
 
            if (pre > 0 && s[i] == '0')
                dp[i] = 1;
            else
                dp[i] = 0;
        }
 
        // Return answer
        return dp[s.Length - 1];
    }
 
    // Driver Code
    public static void Main()
    {
        String S = "01101110";
        int L = 2, R = 3;
 
        if (canReach(S, L, R) == 1)
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by Saurabh

<script>
    // JavaScript program for the above approach
 
    // Function to check if it is possible
    // to reach the end of the binary string
    // using the given jumps
    const canReach = (s, L, R) => {
        // Stores the DP states
        let dp = new Array(s.length).fill(1);
 
        // Stores count of indices from which
        // it is possible to reach index i
        let pre = 0;
 
        // Traverse the given string
        for (let i = 1; i < s.length; i++) {
 
            // Update the values of pre
            // accordingly
            if (i >= L) {
                pre += dp[i - L];
            }
 
            // If the jump size is out of
            // the range [L, R]
            if (i > R) {
                pre -= dp[i - R - 1];
            }
 
            dp[i] = (pre > 0) && (s[i] == '0');
        }
 
        // Return answer
        return dp[s.length - 1];
    }
 
    // Driver Code
    let S = "01101110";
    let L = 2, R = 3;
 
    if (canReach(S, L, R)) document.write("Yes");
    else document.write("No");
 
// This code is contributed by rakeshsahni
 
</script>

No

Complejidad temporal: O(N)
Espacio auxiliar: O(N)