Número de formas de hacer una string binaria de longitud N tal que los ceros siempre aparezcan juntos en grupos de tamaño K

Dados dos números enteros N y K , la tarea es contar el número de formas de hacer una string binaria de longitud N tal que los 0 siempre aparezcan juntos en un grupo de tamaño K.
Ejemplos: 
 

Entrada: N = 3, K = 2 
Salida: 3 
Número de strings binarias: 
111 
100 
001
Entrada: N = 4, K = 2 
Salida: 5 
 

Este problema se puede resolver fácilmente mediante programación dinámica . Sea dp[i] el número de strings binarias de longitud i que satisfacen la condición. 
De la condición se puede deducir que: 
 

• dp[i] = 1 para 1 <= yo < k .
• También dp[k] = 2 ya que una string binaria de longitud K será una string de solo ceros o solo unos.
• Ahora si consideramos para i > k. Si decidimos que el i- ^ésimo carácter sea ‘1’, entonces dp[i] = dp[i-1] ya que el número de strings binarias no cambiaría. Sin embargo, si decidimos que el carácter i ^-ésimo sea ‘0’, entonces requerimos que los caracteres k-1 anteriores también sean ‘0’ y, por lo tanto, dp[i] = dp[ik] . Por lo tanto dp[i] será la suma de estos 2 valores.

Por lo tanto , 
 

dp[i] = dp[i - 1] + dp[i - k]

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

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1000000007;
 
// Function to return no of ways to build a binary
// string of length N such that 0s always occur
// in groups of size K
int noOfBinaryStrings(int N, int k)
{
    int dp[100002];
    for (int i = 1; i <= k - 1; i++) {
        dp[i] = 1;
    }
 
    dp[k] = 2;
 
    for (int i = k + 1; i <= N; i++) {
        dp[i] = (dp[i - 1] + dp[i - k]) % mod;
    }
 
    return dp[N];
}
 
// Driver Code
int main()
{
    int N = 4;
    int K = 2;
    cout << noOfBinaryStrings(N, K);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
static int mod = 1000000007;
 
// Function to return no of ways to build a binary
// string of length N such that 0s always occur
// in groups of size K
static int noOfBinaryStrings(int N, int k)
{
    int dp[] = new int[100002];
    for (int i = 1; i <= k - 1; i++)
    {
        dp[i] = 1;
    }
 
    dp[k] = 2;
 
    for (int i = k + 1; i <= N; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - k]) % mod;
    }
 
    return dp[N];
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 4;
    int K = 2;
    System.out.println(noOfBinaryStrings(N, K));
}
}
 
// This code contributed by Rajput-Ji

# Python3 implementation of the
# above approach
mod = 1000000007;
 
# Function to return no of ways to
# build a binary string of length N
# such that 0s always occur in
# groups of size K
def noOfBinaryStrings(N, k) :
    dp = [0] * 100002;
    for i in range(1, K) :
        dp[i] = 1;
     
    dp[k] = 2;
 
    for i in range(k + 1, N + 1) :
        dp[i] = (dp[i - 1] + dp[i - k]) % mod;
 
    return dp[N];
 
# Driver Code
if __name__ == "__main__" :
 
    N = 4;
    K = 2;
     
    print(noOfBinaryStrings(N, K));
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GFG
{
     
static int mod = 1000000007;
 
// Function to return no of ways to build
// a binary string of length N such that
// 0s always occur in groups of size K
static int noOfBinaryStrings(int N, int k)
{
    int []dp = new int[100002];
    for (int i = 1; i <= k - 1; i++)
    {
        dp[i] = 1;
    }
 
    dp[k] = 2;
 
    for (int i = k + 1; i <= N; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - k]) % mod;
    }
 
    return dp[N];
}
 
// Driver Code
public static void Main()
{
    int N = 4;
    int K = 2;
    Console.WriteLine(noOfBinaryStrings(N, K));
}
}
 
/* This code contributed by PrinciRaj1992 */

<?php
// PHP implementation of the above approach
$mod = 1000000007;
 
// Function to return no of ways to
// build a binary string of length N
// such that 0s always occur in groups
// of size K
function noOfBinaryStrings($N, $k)
{
    global $mod;
    $dp = array(0, 100002, NULL);
    for ($i = 1; $i <= $k - 1; $i++)
    {
        $dp[$i] = 1;
    }
 
    $dp[$k] = 2;
 
    for ($i = $k + 1; $i <= $N; $i++)
    {
        $dp[$i] = ($dp[$i - 1] +
                   $dp[$i - $k]) % $mod;
    }
 
    return $dp[$N];
}
 
// Driver Code
$N = 4;
$K = 2;
echo noOfBinaryStrings($N, $K);
 
// This code is contributed by ita_c
?>

<script>
// Javascript implementation of the approach
 
let mod = 1000000007;
 
// Function to return no of ways to build a binary
// string of length N such that 0s always occur
// in groups of size K
function noOfBinaryStrings(N,k)
{
    let dp = new Array(100002);
    for (let i = 1; i <= k - 1; i++)
    {
        dp[i] = 1;
    }
   
    dp[k] = 2;
   
    for (let i = k + 1; i <= N; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - k]) % mod;
    }
   
    return dp[N];
}
 
// Driver Code
let N = 4;
let K = 2;
document.write(noOfBinaryStrings(N, K));
 
// This code is contributed by rag2127.
</script>

5