Cuente las formas de generar una array de longitud N con 0, 1 y 2 de modo que la suma de todos los productos por pares adyacentes sea K

Dados dos números enteros N y K , la tarea es encontrar el número de arreglos de N longitudes que se pueden generar usando los valores 0 , 1 y 2 cualquier número de veces, tal que la suma de todos los productos por pares adyacentes del arreglo es k _

Ejemplos:

Entrada: N = 4, K = 3
Salida: 5
Explicación: Todos los arreglos posibles son: 

1. arr[] = {2, 1, 1, 0}, suma de productos por pares adyacentes = 2 * 1 + 1 * 1 + 1 * 0 = 3.
2. arr[] = {0, 2, 1, 1}, suma de productos por pares adyacentes = 0 * 2 + 2 * 1 + 1 * 1 = 3.
3. arr[] = {1, 1, 2, 0}, suma de productos por pares adyacentes = 1 * 1 + 1 * 2 + 2 * 0 = 3.
4. arr[] = {0, 1, 1, 2}, la suma de productos por pares adyacentes es 0 * 1 + 1 * 1 + 1 * 2 = 3.
5. arr[] = {1, 1, 1, 1}, suma de productos por pares adyacentes = 1*1 + 1*1 + 1*1 = 3.

Entrada: N = 10, K = 9
Salida: 3445

Enfoque ingenuo: el enfoque más simple es generar todos los arreglos posibles de la array cuyo valor puede ser 0 , 1 o 2 y contar esas arrays cuya suma de productos por pares adyacentes es K. Imprime el recuento de dichos arreglos. 

Complejidad temporal: O(N*3 ^N )
Espacio auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea óptima es utilizar la programación dinámica . Los subproblemas superpuestos se pueden almacenar en una tabla dp[][][] donde dp[i][restante][anterior] almacena la respuesta hasta la posición (N – 1) desde la posición ‘i’ con ‘restante’ como el valor restante para agregar y ‘anterior’ como el número colocado en la posición (i – 1) . Puede haber tres casos posibles para cualquier posición ‘i’:

• Asigne ‘0’ a la posición ‘i’.
• Asigne ‘1’ a la posición ‘i’.
• Asigne ‘2’ a la posición ‘i’.

Siga los pasos a continuación para resolver el problema:

• Inicialice el dp[][][] para almacenar la posición actual, el valor restante para agregar y el elemento en la posición anterior.
• El estado de transición es el siguiente:

dp[i][remaining_sum][previous_element] = dp(asignar 0 a pos ‘i’) + dp(asignar 1 a ‘i’ ) + dp(asignar 2 a ‘i’) 

• Resuelva la relación de recurrencia anterior recursivamente y almacene el resultado para cada estado en la tabla dp . Para la superposición, los subproblemas utilizan el resultado almacenado en la tabla dp .
• Después de que finalicen las llamadas recursivas anteriores, imprima el número total de arrays que tienen productos adyacentes por pares de la array es K devuelto por la función.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find total number of
// possible arrangements of array
int waysForPairwiseSumToBeK(
    int i, int rem, int previous,
    int N, int dp[][15][3])
{
    // Base Case
    if (i == N) {
        if (rem == 0)
            return 1;
        else
            return 0;
    }
 
    // If rem exceeds 'k' return 0
    if (rem < 0)
        return 0;
 
    // Return the already calculated
    // states
    if (dp[i][rem][previous] != -1)
        return dp[i][rem][previous];
 
    int ways = 0;
 
    // Place a '0' at current position
    ways += waysForPairwiseSumToBeK(
        i + 1, rem, 0, N, dp);
 
    // Place a '1' at current position
    // Add it to previous value
    ways += waysForPairwiseSumToBeK(
        i + 1, rem - (previous), 1, N, dp);
 
    // Place a '2' at current position.
    // Add it to previous value.
    ways += waysForPairwiseSumToBeK(
        i + 1, rem - (2 * previous), 2, N, dp);
 
    // Store the current state result
    // return the same result
    return dp[i][rem][previous] = ways;
}
 
// Function to find number of possible
// arrangements of array with 0, 1, and
// 2 having pairwise product sum K
void countOfArrays(int i, int rem,
                   int previous, int N)
{
    // Store the overlapping states
    int dp[15][15][3];
 
    // Initialize dp table with -1
    memset(dp, -1, sizeof dp);
 
    // Stores total number of ways
    int totWays
        = waysForPairwiseSumToBeK(
            i, rem, previous, N, dp);
 
    // Print number of ways
    cout << totWays << ' ';
}
 
// Driver Code
int main()
{
    // Given N and K
    int N = 4, K = 3;
 
    // Function Call
    countOfArrays(0, K, 0, N);
 
    return 0;
}

// Java program for the
// above approach
import java.util.*;
class solution{
   
// Function to find total number of
// possible arrangements of array
static int waysForPairwiseSumToBeK(int i, int rem,
                                   int previous,
                                   int N, int [][][]dp)
{
  // Base Case
  if (i == N)
  {
    if (rem == 0)
      return 1;
    else
      return 0;
  }
 
  // If rem exceeds
  // 'k' return 0
  if (rem < 0)
    return 0;
 
  // Return the already
  // calculated states
  if (dp[i][rem][previous] != -1)
    return dp[i][rem][previous];
 
  int ways = 0;
 
  // Place a '0' at current position
  ways += waysForPairwiseSumToBeK(i + 1, rem,
                                  0, N, dp);
 
  // Place a '1' at current position
  // Add it to previous value
  ways += waysForPairwiseSumToBeK(i + 1, rem -
                                  (previous),
                                  1, N, dp);
 
  // Place a '2' at current position.
  // Add it to previous value.
  ways += waysForPairwiseSumToBeK(i + 1, rem -
                                  (2 * previous),
                                  2, N, dp);
 
  // Store the current state result
  // return the same result
  dp[i][rem][previous] = ways;
  return ways;
}
 
// Function to find number of possible
// arrangements of array with 0, 1, and
// 2 having pairwise product sum K
static void countOfArrays(int i, int rem,
                          int previous, int N)
{
  // Store the overlapping states
  int [][][]dp = new int[15][15][3];
 
  // Initialize dp table with -1
  for(int p = 0; p < 15; p++)
  {
    for(int q = 0; q < 15; q++)
    {     
      for(int r = 0; r < 3; r++)
        dp[p][q][r] = -1;
    }
  }
 
  // Stores total number of ways
  int totWays = waysForPairwiseSumToBeK(i, rem,
                                        previous,
                                        N, dp);
  // Print number of ways
  System.out.print(totWays);
}
 
// Driver Code
public static void main(String args[])
{
  // Given N and K
  int N = 4, K = 3;
 
  // Function Call
  countOfArrays(0, K, 0, N);
}
}
 
// This code is contributed by SURENDRA_GANGWAR

# Python3 program for the above approach
 
# Function to find total number of
# possible arrangements of array
def waysForPairwiseSumToBeK(i, rem, previous, N, dp):
     
    # Base Case
    if (i == N):
        if (rem == 0):
            return 1
        else:
            return 0
 
    # If rem exceeds 'k' return 0
    if (rem < 0):
        return 0
         
    # Return the already calculated
    # states
    if (dp[i][rem][previous] != -1):
        return dp[i][rem][previous]
         
    ways = 0
 
    # Place a '0' at current position
    ways += waysForPairwiseSumToBeK(i + 1, rem,
                                    0, N, dp)
 
    # Place a '1' at current position
    # Add it to previous value
    ways += waysForPairwiseSumToBeK(i + 1,
                                  rem - (previous),
                                  1, N, dp)
 
    # Place a '2' at current position.
    # Add it to previous value.
    ways += waysForPairwiseSumToBeK(i + 1,
                             rem - (2 * previous),
                             2, N, dp)
 
    # Store the current state result
    # return the same result
    dp[i][rem][previous] = ways
     
    return ways
 
# Function to find number of possible
# arrangements of array with 0, 1, and
# 2 having pairwise product sum K
def countOfArrays(i, rem, previous, N):
     
    # Store the overlapping states
    dp = [[[-1 for i in range(3)]
               for j in range(15)]
               for k in range(15)]
 
    # Stores total number of ways
    totWays = waysForPairwiseSumToBeK(i, rem,
                                      previous,
                                      N, dp)
 
    # Print number of ways
    print(totWays, end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given N and K
    N = 4
    K = 3
 
    # Function Call
    countOfArrays(0, K, 0, N)
 
# This code is contributed by bgangwar59

// C# program for the
// above approach
using System;
 
class GFG{
   
// Function to find total number of
// possible arrangements of array
static int waysForPairwiseSumToBeK(int i, int rem,
                                   int previous,
                                   int N, int [,,]dp)
{
   
  // Base Case
  if (i == N)
  {
    if (rem == 0)
      return 1;
    else
      return 0;
  }
   
  // If rem exceeds
  // 'k' return 0
  if (rem < 0)
    return 0;
 
  // Return the already
  // calculated states
  if (dp[i, rem, previous] != -1)
    return dp[i, rem, previous];
 
  int ways = 0;
 
  // Place a '0' at current position
  ways += waysForPairwiseSumToBeK(i + 1, rem,
                                  0, N, dp);
 
  // Place a '1' at current position
  // Add it to previous value
  ways += waysForPairwiseSumToBeK(i + 1, rem -
                                  (previous),
                                  1, N, dp);
 
  // Place a '2' at current position.
  // Add it to previous value.
  ways += waysForPairwiseSumToBeK(i + 1, rem -
                                  (2 * previous),
                                   2, N, dp);
 
  // Store the current state result
  // return the same result
  dp[i, rem, previous] = ways;
   
  return ways;
}
 
// Function to find number of possible
// arrangements of array with 0, 1, and
// 2 having pairwise product sum K
static void countOfArrays(int i, int rem,
                          int previous, int N)
{
   
  // Store the overlapping states
  int [,,]dp = new int[ 15, 15, 3 ];
 
  // Initialize dp table with -1
  for(int p = 0; p < 15; p++)
  {
    for(int q = 0; q < 15; q++)
    {     
      for(int r = 0; r < 3; r++)
        dp[p, q, r] = -1;
    }
  }
 
  // Stores total number of ways
  int totWays = waysForPairwiseSumToBeK(i, rem,
                                        previous,
                                        N, dp);
   
  // Print number of ways
  Console.Write(totWays);
}
 
// Driver Code
public static void Main(String []args)
{
   
  // Given N and K
  int N = 4, K = 3;
 
  // Function Call
  countOfArrays(0, K, 0, N);
}
}
 
// This code is contributed by gauravrajput1

<script>
// Javascript program for the
// above approach
 
// Function to find total number of
// possible arrangements of array
function waysForPairwiseSumToBeK(i,rem,previous,N,dp)
{
    // Base Case
  if (i == N)
  {
    if (rem == 0)
      return 1;
    else
      return 0;
  }
  
  // If rem exceeds
  // 'k' return 0
  if (rem < 0)
    return 0;
  
  // Return the already
  // calculated states
  if (dp[i][rem][previous] != -1)
    return dp[i][rem][previous];
  
  let ways = 0;
  
  // Place a '0' at current position
  ways += waysForPairwiseSumToBeK(i + 1, rem,
                                  0, N, dp);
  
  // Place a '1' at current position
  // Add it to previous value
  ways += waysForPairwiseSumToBeK(i + 1, rem -
                                  (previous),
                                  1, N, dp);
  
  // Place a '2' at current position.
  // Add it to previous value.
  ways += waysForPairwiseSumToBeK(i + 1, rem -
                                  (2 * previous),
                                  2, N, dp);
  
  // Store the current state result
  // return the same result
  dp[i][rem][previous] = ways;
  return ways;
}
 
// Function to find number of possible
// arrangements of array with 0, 1, and
// 2 having pairwise product sum K
function countOfArrays(i,rem,previous,N)
{
    // Store the overlapping states
  let dp = new Array(15);
  for(let i = 0; i < 15; i++)
  {
      dp[i] = new Array(15);
    for(let j = 0; j < 15; j++)
    {
        dp[i][j] = new Array(3);
        for(let k = 0; k < 3; k++)
            dp[i][j][k] = -1;
    }
  }
  
  // Stores total number of ways
  let totWays = waysForPairwiseSumToBeK(i, rem,
                                        previous,
                                        N, dp);
  // Print number of ways
  document.write(totWays);
}
 
// Driver Code
// Given N and K
let N = 4, K = 3;
 
// Function Call
countOfArrays(0, K, 0, N);
 
// This code is contributed by patel2127
</script>

5

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