Dado un número entero N , la tarea es contar el número de strings binarias posibles de modo que no haya una substring de longitud ≥ 3 de todos los 1. Este recuento puede llegar a ser muy grande, así que imprima la respuesta módulo 10 9 + 7 .
Ejemplos:
Entrada: N = 4
Salida: 13
Todas las strings válidas posibles son 0000, 0001, 0010, 0100,
1000, 0101, 0011, 1010, 1001, 0110, 1100, 1101 y 1011.
Entrada: N = 2
Salida: 4
Enfoque: para cada valor de 1 a N , las únicas strings requeridas son en las que el número de substrings en las que ‘1’ aparece consecutivamente solo dos veces, una vez o cero veces. Esto se puede calcular de 2 a N recursivamente. La programación dinámica se puede utilizar para la memorización donde dp[i][j] almacenará el número de posibles strings de forma que 1 aparezca consecutivamente j veces hasta el i -ésimo índice y j será 0, 1, 2, …, i (puede variar de 1 a N ).
dp[i][0] = dp[i – 1][0] + dp[i – 1][1] + dp[i – 1][2] como en la posición i , se pondrá 0 .
dp[i][1] = dp[i – 1][0] ya que no hay 1 en la (i – 1) ésima posición, entonces tomamos ese valor.
dp[i][2] = dp[i – 1][1] ya que el primer 1 apareció en (i – 1) la posición th (consecutivamente) así que tomamos ese valor directamente.
Los casos base son para una string de longitud 1, es decir , dp[1][0] = 1 , dp[1][1] = 1 , dp[1][2] = 0 . Entonces, encuentre todo el valor dp[N][0] + dp[N][1] + dp[N][2] y la suma de todos los casos posibles en el Nª posición.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const long MOD = 1000000007;
// Function to return the count of
// all possible binary strings
long countStr(long N)
{
long dp[N + 1][3];
// Fill 0's in the dp array
memset(dp, 0, sizeof(dp));
// Base cases
dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 0;
for (int i = 2; i <= N; i++) {
// dp[i][j] is the number of possible
// strings such that '1' just appeared
// consecutively j times upto ith index
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]
+ dp[i - 1][2])
% MOD;
// Taking previously calculated value
dp[i][1] = dp[i - 1][0] % MOD;
dp[i][2] = dp[i - 1][1] % MOD;
}
// Taking all the possible cases that
// can appear at the Nth position
long ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD;
return ans;
}
// Driver code
int main()
{
long N = 8;
cout << countStr(N);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
final static long MOD = 1000000007;
// Function to return the count of
// all possible binary strings
static long countStr(int N)
{
long dp[][] = new long[N + 1][3];
// Fill 0's in the dp array
//memset(dp, 0, sizeof(dp));
// Base cases
dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 0;
for (int i = 2; i <= N; i++)
{
// dp[i][j] is the number of possible
// strings such that '1' just appeared
// consecutively j times upto ith index
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]
+ dp[i - 1][2]) % MOD;
// Taking previously calculated value
dp[i][1] = dp[i - 1][0] % MOD;
dp[i][2] = dp[i - 1][1] % MOD;
}
// Taking all the possible cases that
// can appear at the Nth position
long ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD;
return ans;
}
// Driver code
public static void main (String[] args)
{
int N = 8;
System.out.println(countStr(N));
}
}
// This code is contributed by AnkitRai01
Python
# Python3 implementation of the approach MOD = 1000000007 # Function to return the count of # all possible binary strings def countStr(N): dp = [[0 for i in range(3)] for i in range(N + 1)] # Base cases dp[1][0] = 1 dp[1][1] = 1 dp[1][2] = 0 for i in range(2, N + 1): # dp[i][j] is the number of possible # strings such that '1' just appeared # consecutively j times upto ith index dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD # Taking previously calculated value dp[i][1] = dp[i - 1][0] % MOD dp[i][2] = dp[i - 1][1] % MOD # Taking all the possible cases that # can appear at the Nth position ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD return ans # Driver code if __name__ == '__main__': N = 8 print(countStr(N)) # This code is contributed by mohit kumar 29
C#
// C# implementation of the approach
using System;
class GFG
{
static long MOD = 1000000007;
// Function to return the count of
// all possible binary strings
static long countStr(int N)
{
long [,]dp = new long[N + 1, 3];
// Base cases
dp[1, 0] = 1;
dp[1, 1] = 1;
dp[1, 2] = 0;
for (int i = 2; i <= N; i++)
{
// dp[i,j] is the number of possible
// strings such that '1' just appeared
// consecutively j times upto ith index
dp[i, 0] = (dp[i - 1, 0] + dp[i - 1, 1]
+ dp[i - 1, 2]) % MOD;
// Taking previously calculated value
dp[i, 1] = dp[i - 1, 0] % MOD;
dp[i, 2] = dp[i - 1, 1] % MOD;
}
// Taking all the possible cases that
// can appear at the Nth position
long ans = (dp[N, 0] + dp[N, 1] + dp[N, 2]) % MOD;
return ans;
}
// Driver code
public static void Main ()
{
int N = 8;
Console.WriteLine(countStr(N));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
var MOD = 1000000007;
// Function to return the count of
// all possible binary strings
function countStr(N)
{
var dp = Array.from(Array(N+1), ()=> Array(3).fill(0));
// Base cases
dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 0;
for (var i = 2; i <= N; i++) {
// dp[i][j] is the number of possible
// strings such that '1' just appeared
// consecutively j times upto ith index
dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]
+ dp[i - 1][2])
% MOD;
// Taking previously calculated value
dp[i][1] = dp[i - 1][0] % MOD;
dp[i][2] = dp[i - 1][1] % MOD;
}
// Taking all the possible cases that
// can appear at the Nth position
var ans = (dp[N][0] + dp[N][1] + dp[N][2]) % MOD;
return ans;
}
// Driver code
var N = 8;
document.write( countStr(N));
// This code is contributed by itsok.
</script>
149
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)