Cuente las formas de colocar mosaicos en un tablero de N longitud usando mosaicos de dimensiones específicas

Dado un número entero N , la tarea es colocar mosaicos en un tablero de dimensiones N * 1 . La tarea es contar el número de formas de colocar mosaicos en un tablero usando mosaicos de dimensiones 1 * 1 y 2 * 1 .

Ejemplos:

Entrada: N = 2 
Salida: 5 
Explicación: 
Teselar el tablero de tamaño 2 x 1 colocando 1 x 1 teja de forma Horizontal y otra teja de 1 x 1 de forma vertical. 
Embaldosa el tablero de tamaño 2 x 1 colocando 1 baldosa de 1 x 1 de forma vertical y otra baldosa de 1 x 1 de forma horizontal. 
Embaldosa el tablero de tamaño 2 x 1 colocando una baldosa de 1 x 1 de forma Horizontal y otra baldosa de 1 x 1 de forma Horizontal. 
Embaldosa el tablero de tamaño 2 x 1 colocando una baldosa de 1 x 1 de forma vertical y otra baldosa de 1 x 1 de forma vertical. 
Embaldosa el tablero de tamaño 2 x 1 colocando baldosas de 2 x 1 de forma horizontal. 
Por lo tanto, la salida requerida es 5.

Entrada: N = 1
Salida: 2

Planteamiento: El problema se puede resolver usando Programación Dinámica . La idea es dividir el tablero N x 1 en tableros más pequeños, luego contar las formas de colocar mosaicos en los tableros más pequeños. Finalmente, imprima el recuento total de formas de teselar el tablero N x 1 . Siga los pasos a continuación para resolver el problema:

• Las siguientes son las tres formas de colocar la primera ficha: 
  • Coloque el mosaico de 1 x 1 verticalmente.
  • Coloque el mosaico de 1 x 1 horizontalmente.
  • Coloque el azulejo de 2 x 1 horizontalmente.
• Por lo tanto, la relación de recurrencia para resolver el problema es la siguiente:

víascnt(N) = 2 * víascnt(N – 1) + víascnt(N – 2)

• Inicialice una array, por ejemplo, dp[] , donde dp[i] almacena el recuento de formas de colocar mosaicos en el tablero ix 1 .
• Iterar sobre el rango [2, N] y llenar la array, dp[] usando el método de tabulación .
• Finalmente, imprima el valor de dp[N] .

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

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
 
// Function to count the ways to tile N * 1
// board using 1 * 1 and 2 * 1 tiles
long countWaysToTileBoard(long N)
{
     
    // dp[i]: Stores count of ways to tile
    // i * 1 board using given tiles
    long dp[N + 1];
 
    // Base Case
    dp[0] = 1;
    dp[1] = 2;
     
    // Iterate over the range [2, N]
    for (int i = 2; i <= N; i++) {
 
        // Fill dp[i] using
        // the recurrence relation
        dp[i] = (2 * dp[i - 1]
                    + dp[i - 2] );
    }
 
    cout << dp[N];
}
 
 
 
// Driver Code
int main()
{
    // Given N
    long N = 2;
 
    // Function Call
    countWaysToTileBoard(N);
 
    return 0;
}

// Java program to implement
// the above approach
class GFG{
     
// Function to count the ways to tile N * 1
// board using 1 * 1 and 2 * 1 tiles
static void countWaysToTileBoard(int N)
{
     
    // dp[i]: Stores count of ways to tile
    // i * 1 board using given tiles
    int dp[] = new int[N + 1];
     
    // Base Case
    dp[0] = 1;
    dp[1] = 2;
     
    // Iterate over the range [2, N]
    for(int i = 2; i <= N; i++)
    {
         
        // Fill dp[i] using
        // the recurrence relation
        dp[i] = (2 * dp[i - 1] +
                     dp[i - 2]);
    }
    System.out.print(dp[N]);
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given N
    int N = 2;
     
    // Function Call
    countWaysToTileBoard(N);
}
}
 
// This code is contributed by AnkThon

# Python3 program to implement
# the above approach
 
# Function to count the ways to tile N * 1
# board using 1 * 1 and 2 * 1 tiles
def countWaysToTileBoard( N) :
     
    # dp[i]: Stores count of ways to tile
    # i * 1 board using given tiles
    dp = [0]*(N + 1)
 
    # Base Case
    dp[0] = 1
    dp[1] = 2
     
    # Iterate over the range [2, N]
    for i in range(2, N + 1) :
 
        # Fill dp[i] using
        # the recurrence relation
        dp[i] = (2 * dp[i - 1] + dp[i - 2] )
     
    print(dp[N])
 
# Driver Code
if __name__ == "__main__" :
     
    # Given N
    N = 2
 
    # Function Call
    countWaysToTileBoard(N)
     
  # This code is contributed by jana_sayantan 

// C# program to implement
// the above approach
using System;
 
class GFG{
     
// Function to count the ways to tile N * 1
// board using 1 * 1 and 2 * 1 tiles
static void countWaysToTileBoard(int N)
{
     
    // dp[i]: Stores count of ways to tile
    // i * 1 board using given tiles
    int []dp = new int[N + 1];
     
    // Base Case
    dp[0] = 1;
    dp[1] = 2;
     
    // Iterate over the range [2, N]
    for(int i = 2; i <= N; i++)
    {
         
        // Fill dp[i] using
        // the recurrence relation
        dp[i] = (2 * dp[i - 1] +
                     dp[i - 2]);
    }
    Console.Write(dp[N]);
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given N
    int N = 2;
     
    // Function Call
    countWaysToTileBoard(N);
}
}
 
// This code is contributed by shikhasingrajput

<script>
 
// JavaScript program for above approach
 
// Function to count the ways to tile N * 1
// board using 1 * 1 and 2 * 1 tiles
function countWaysToTileBoard(N)
{
      
    // dp[i]: Stores count of ways to tile
    // i * 1 board using given tiles
    let dp = [];
      
    // Base Case
    dp[0] = 1;
    dp[1] = 2;
      
    // Iterate over the range [2, N]
    for(let i = 2; i <= N; i++)
    {
          
        // Fill dp[i] using
        // the recurrence relation
        dp[i] = (2 * dp[i - 1] +
                     dp[i - 2]);
    }
    document.write(dp[N]);
}
  
 
// Driver Code
 
     // Given N
    let N = 2;
      
    // Function Call
    countWaysToTileBoard(N);
           
</script>

5

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