Recuento de strings binarias que tienen como máximo X 1 consecutivos e Y 0 consecutivos

Posted on by Rudeus Greyrat

Dados dos números enteros N y M (1 ≤ N, M ≤ 100) que denotan el número total de 1 y 0 respectivamente. La tarea es contar el número de arreglos posibles de estos 0 y 1 de tal manera que cualquier arreglo tenga como máximo X 1 consecutivos e Y 0 consecutivos (1 ≤ X, Y ≤ 10) . Como el número de arreglos puede ser muy grande, calcule la respuesta con MODULO 10 9 +7 .

Ejemplos:

 Entrada: N = 2, M = 3, X = 1, Y = 2
Salida: 5
Explicación: Todos los arreglos: 11000, 10100, 10010, 10001, 01100, 01010, 01001, 00110, 00101, 00011.
De estos arreglos el los arreglos válidos son: 10100, 10010, 01010, 01001, 00101
Entonces el número de arreglos posibles es 5.

Entrada: N = 2, M = 2, X = 1, Y = 1
Salida: 2

 

Intuición:

  • La intuición básica del problema es verificar todos los arreglos posibles usando la recursividad.
  • Esto conduce a una complejidad temporal extremadamente alta.
  • Así que necesito alguna técnica de optimización.
  • Tabulación de opciones. Esto reduce la complejidad general del problema por un factor drástico.
  • El uso de un enfoque iterativo sobre la recursión tradicional + memorización lo hace aún más simple.

Enfoque: Basado en la intuición anterior, este problema se puede resolver utilizando el enfoque de programación dinámica . Siga los pasos que se mencionan a continuación para resolver el problema.

  • Utilice una cuadrícula 3D para almacenar lo siguiente {recuento de 1, recuento de 0, representa el último valor que se utilizó (0 si A, 1 si B) }
  • Use bucle anidado para 1 y 0.
  • En cada iteración en bucle anidado, (i denota 1s, j denota 0s)
    • Si se agregan 1s a la secuencia actual, agregue el número de secuencias formadas con i – k, (1 ≤ k ≤ X) 1s y termina con 0s.
    • Si se agregan 0 a la secuencia actual, agregue el número de secuencias formadas con j – k, (1 ≤ k ≤ Y) 0 y termina con 1.
  • Esto da la respuesta a cada iteración de secuencia con i 1s yj 0s.

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

C++

// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
 
// Functiont to calculate
// total possible arrangements
int totalArrangements(int N, int M,
                      int X, int Y)
{
    int dp[N + 1][M + 1][2];
    int mod = 1000000007;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            dp[i][j][0] = 0;
            dp[i][j][1] = 0;
        }
    }
    dp[0][0][0] = 1;
    dp[0][0][1] = 1;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            for (int k = 1; k <= X; k++) {
                if (i >= k) {
                    dp[i][j][1]
                        += dp[i - k][j][0];
                    dp[i][j][1] %= mod;
                }
            }
            for (int k = 1; k <= Y; k++) {
                if (j >= k) {
                    dp[i][j][0]
                        += dp[i][j - k][1];
                    dp[i][j][0] %= mod;
                }
            }
        }
    }
    return ((dp[N][M][0] + dp[N][M][1]) % mod);
}
 
// Driver code
int main()
{
    int N = 2, M = 3, X = 1, Y = 2;
     
    cout << totalArrangements(N, M, X, Y);
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
 
class GFG{
 
// Functiont to calculate
// total possible arrangements
static int totalArrangements(int N, int M,
                      int X, int Y)
{
    int dp[][][] = new int[N + 1][M + 1][2];
    int mod = 1000000007;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            dp[i][j][0] = 0;
            dp[i][j][1] = 0;
        }
    }
    dp[0][0][0] = 1;
    dp[0][0][1] = 1;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            for (int k = 1; k <= X; k++) {
                if (i >= k) {
                    dp[i][j][1]
                        += dp[i - k][j][0];
                    dp[i][j][1] %= mod;
                }
            }
            for (int k = 1; k <= Y; k++) {
                if (j >= k) {
                    dp[i][j][0]
                        += dp[i][j - k][1];
                    dp[i][j][0] %= mod;
                }
            }
        }
    }
    return ((dp[N][M][0] + dp[N][M][1]) % mod);
}
 
// Driver Code
public static void main(String[] args)
{
     int N = 2, M = 3, X = 1, Y = 2;
     
    System.out.print(totalArrangements(N, M, X, Y));
}
}
 
// This code is contributed by sanjoy_62.

Python3

# Python code to implement above approach
 
# Functiont to calculate
# total possible arrangements
def totalArrangements(N, M, X, Y):
    dp = [[[0 for i in range(2)] for j in range(M + 1) ] for k in range(N + 1)]
    mod = 1000000007;
    for i in range(N + 1):
        for j in range(M + 1):
            dp[i][j][0] = 0;
            dp[i][j][1] = 0;
    dp[0][0][0] = 1;
    dp[0][0][1] = 1;
    for i in range(N + 1):
        for j in range(M + 1):
            for k in range(1, X + 1):
                if (i >= k):
                    dp[i][j][1] += dp[i - k][j][0];
                    dp[i][j][1] %= mod;
            for k in range(1, Y + 1):
                if (j >= k):
                    dp[i][j][0] += dp[i][j - k][1];
                    dp[i][j][0] %= mod;
    return ((dp[N][M][0] + dp[N][M][1]) % mod);
 
# Driver code
N = 2
M = 3
X = 1
Y = 2;
print(totalArrangements(N, M, X, Y));
 
# This code is contributed by gfgking

C#

using System;
 
public class GFG{
 
  // Functiont to calculate
  // total possible arrangements
  static int totalArrangements(int N, int M,
                               int X, int Y)
  {
    int[,,] dp = new int[N + 1, M + 1, 2];
    int mod = 1000000007;
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= M; j++) {
        dp[i, j, 0] = 0;
        dp[i, j, 1] = 0;
      }
    }
    dp[0, 0, 0] = 1;
    dp[0, 0, 1] = 1;
    for (int i = 0; i <= N; i++) {
      for (int j = 0; j <= M; j++) {
        for (int k = 1; k <= X; k++) {
          if (i >= k) {
            dp[i, j, 1]
              += dp[i - k, j, 0];
            dp[i, j, 1] %= mod;
          }
        }
        for (int k = 1; k <= Y; k++) {
          if (j >= k) {
            dp[i, j, 0]
              += dp[i, j-k, 1];
            dp[i, j, 0] %= mod;
          }
        }
      }
    }
    return ((dp[N, M, 0] + dp[N, M,1]) % mod);
  }
 
  // Driver code
  static public void Main ()
  {
 
    int N = 2, M = 3, X = 1, Y = 2;
    Console.WriteLine(totalArrangements(N, M, X, Y));
  }
}
 
// This code is contributed by hrithikgarg03188.

Javascript

<script>
    // JavaScript code to implement above approach
 
    // Functiont to calculate
    // total possible arrangements
    const totalArrangements = (N, M, X, Y) => {
        let dp = new Array(N + 1).fill(0).map(() => new Array(M + 1).fill(0).map(() => new Array(2)));
        let mod = 1000000007;
        for (let i = 0; i <= N; i++) {
            for (let j = 0; j <= M; j++) {
                dp[i][j][0] = 0;
                dp[i][j][1] = 0;
            }
        }
        dp[0][0][0] = 1;
        dp[0][0][1] = 1;
        for (let i = 0; i <= N; i++) {
            for (let j = 0; j <= M; j++) {
                for (let k = 1; k <= X; k++) {
                    if (i >= k) {
                        dp[i][j][1]
                            += dp[i - k][j][0];
                        dp[i][j][1] %= mod;
                    }
                }
                for (let k = 1; k <= Y; k++) {
                    if (j >= k) {
                        dp[i][j][0]
                            += dp[i][j - k][1];
                        dp[i][j][0] %= mod;
                    }
                }
            }
        }
        return ((dp[N][M][0] + dp[N][M][1]) % mod);
    }
 
    // Driver code
    let N = 2, M = 3, X = 1, Y = 2;
    document.write(totalArrangements(N, M, X, Y));
 
// This code is contributed by rakeshsahni
 
</script>
Producción

5

Complejidad temporal: O(N * M * (X+Y)).
Espacio Auxiliar: O(N * M)

Publicación traducida automáticamente

Artículo escrito por bjsreddy742002 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *