Dado un número entero N , la tarea es contar el número de strings binarias posibles de longitud N que no contengan «111» como substring. La respuesta podría ser grande, así que imprima la respuesta módulo 10 9 + 7 .
Ejemplos:
Entrada: N = 3
Salida: 7
Todas las substrings posibles son “000”, “001”,
“010”, “011”, “100”, “101” y “110”.
«111» no es una string válida.
Entrada N = 16
Salida: 19513
Enfoque: La programación dinámica se puede utilizar para resolver este problema. Cree una array dp[][] donde dp[i][j] almacenará el recuento de posibles substrings de modo que 1 aparezca j veces consecutivas hasta el i-ésimo índice. Ahora, las relaciones de recurrencia serán:
dp[i][0] = dp[i – 1][0] + dp[i – 1][1] + dp[i – 1][2]
dp[i][1] = dp[i – 1 ][0]
pd[i][2] = pd[i – 1][1]
Y los casos base serán dp[1][0] = 1 , dp[1][1] = 1 y dp[1][2] = 0 . Ahora, el conteo requerido de strings será dp[N][0] + dp[N][1] + dp[N][2] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
const long MOD = 1000000007;
// Function to return the count
// of all possible valid strings
long countStrings(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] = number of possible strings
// such that '1' just appeared consecutively
// j times upto the 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 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 = 3;
cout << countStrings(N);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
final static int MOD = 1000000007;
// Function to return the count
// of all possible valid strings
static long countStrings(int N)
{
int i, j;
int dp[][] = new int[N + 1][3];
// Fill 0's in the dp array
for(i = 0; i < N + 1; i++)
{
for(j = 9; j < 3 ; j ++)
{
dp[i][j] = 0;
}
}
// Base cases
dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 0;
for (i = 2; i <= N; i++)
{
// dp[i][j] = number of possible strings
// such that '1' just appeared consecutively
// j times upto the 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 possible cases that
// can appear at the Nth position
int ans = (dp[N][0] + dp[N][1] +
dp[N][2]) % MOD;
return ans;
}
// Driver code
public static void main (String[] args)
{
int N = 3;
System.out.println(countStrings(N));
}
}
// This code is contributed by AnkitRai01
Python3
# Python3 implementation of the approach MOD = 1000000007 # Function to return the count # of all possible valid strings def countStrings(N): # Initialise and fill 0's in the dp array dp = [[0] * 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] = number of possible strings # such that '1' just appeared consecutively # j times upto the 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 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 = 3 print(countStrings(N)) # This code is contributed by ashutosh450
C#
// C# implementation of the above approach
using System;
class GFG
{
static readonly int MOD = 1000000007;
// Function to return the count
// of all possible valid strings
static long countStrings(int N)
{
int i, j;
int [,]dp = new int[N + 1, 3];
// Fill 0's in the dp array
for(i = 0; i < N + 1; i++)
{
for(j = 9; j < 3; j ++)
{
dp[i, j] = 0;
}
}
// Base cases
dp[1, 0] = 1;
dp[1, 1] = 1;
dp[1, 2] = 0;
for (i = 2; i <= N; i++)
{
// dp[i,j] = number of possible strings
// such that '1' just appeared consecutively
// j times upto the 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 possible cases that
// can appear at the Nth position
int ans = (dp[N, 0] + dp[N, 1] +
dp[N, 2]) % MOD;
return ans;
}
// Driver code
public static void Main (String[] args)
{
int N = 3;
Console.WriteLine(countStrings(N));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript implementation of the approach
var MOD = 1000000007;
// Function to return the count
// of all possible valid strings
function countStrings(N)
{
var i, j;
var dp = Array(N+1).fill(0).map(x => Array(3).fill(0));
// Fill 0's in the dp array
for(i = 0; i < N + 1; i++)
{
for(j = 9; j < 3 ; j ++)
{
dp[i][j] = 0;
}
}
// Base cases
dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 0;
for (i = 2; i <= N; i++)
{
// dp[i][j] = number of possible strings
// such that '1' just appeared consecutively
// j times upto the 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 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 = 3;
document.write(countStrings(N));
// This code is contributed by 29AjayKumar
</script>
Producción:
7
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)