Recuento de arrays que tienen elementos consecutivos con diferentes valores

Dados tres enteros positivos n , k y x . La tarea es contar el número de arrays diferentes que se pueden formar de tamaño n, de modo que cada elemento esté entre 1 y k y dos elementos consecutivos sean diferentes. Además, el primer y último elemento de cada array deben ser 1 y x respectivamente.

Ejemplos: 

Input : n = 4, k = 3, x = 2
Output : 3

La idea es utilizar Programación Dinámica y combinatoria para resolver el problema. 
En primer lugar, observe que la respuesta es la misma para todo x desde 2 hasta k. Se puede demostrar fácilmente. Esto será útil más adelante. 
Sea el estado f(i) el número de formas de llenar el rango [1, i] del arreglo A tal que A ₁ = 1 y A _i ≠ 1. 
Por lo tanto, si x ≠ 1, la respuesta al problema es f (n)/(k – 1), porque f(n) es el número de formas en que A _n se llena con un número de 2 a k, y la respuesta es igual para todos esos valores A _n , por lo que la respuesta para an el valor individual es f(n)/(k – 1). 
De lo contrario, si x = 1, la respuesta es f(n – 1), porque A _{n – 1} ≠ 1, y el único número que podemos llenar A_n con es x = 1. 

Ahora, el principal problema es cómo calcular f(i). Considere todos los números que A _{i – 1} puede ser. Sabemos que debe estar en [1, k]. 

• Si A _{i – 1} ≠ 1, entonces hay (k – 2)f(i – 1) formas de llenar el resto del arreglo, porque A _i no puede ser 1 o A _{i – 1} (así que multiplicamos con (k – 2)), y para el rango [1, i – 1], hay, recursivamente, f(i – 1) formas.
• Si A _{i – 1} = 1, entonces hay (k – 1)f(i – 2) formas de completar el resto de la array, porque A _{i – 1} = 1 significa A _{i – 2} ≠ 1, lo que significa que hay f(i – 2) formas de completar el rango [1, i – 2] y el único valor que A _i no puede ser 1, por lo que tenemos (k – 1) opciones para A _i .

Combinando lo anterior, obtenemos 

f(i) = (k - 1) * f(i - 2) + (k - 2) * f(i - 1)

Esto nos ayudará a usar programación dinámica usando f(i).

A continuación se muestra la implementación de este enfoque:  

// CPP Program to find count of arrays.
#include <bits/stdc++.h>
#define MAXN 109
using namespace std;
 
// Return the number of arrays with given constartints.
int countarray(int n, int k, int x)
{
    int dp[MAXN] = { 0 };
 
    // Initialising dp[0] and dp[1].
    dp[0] = 0;
    dp[1] = 1;
 
    // Computing f(i) for each 2 <= i <= n.
    for (int i = 2; i < n; i++)
        dp[i] = (k - 2) * dp[i - 1] +
                (k - 1) * dp[i - 2];
 
    return (x == 1 ? (k - 1) * dp[n - 2] : dp[n - 1]);
}
 
// Driven Program
int main()
{
    int n = 4, k = 3, x = 2;
    cout << countarray(n, k, x) << endl;
    return 0;
}

// Java program to find count of arrays.
import java.util.*;
 
class Counting
{
    static int MAXN = 109;
 
    public static int countarray(int n, int k,
                                       int x)
    {
        int[] dp = new int[109];
 
        // Initialising dp[0] and dp[1].
        dp[0] = 0;
        dp[1] = 1;
 
        // Computing f(i) for each 2 <= i <= n.
        for (int i = 2; i < n; i++)
            dp[i] = (k - 2) * dp[i - 1] +
                (k - 1) * dp[i - 2];
 
        return (x == 1 ? (k - 1) * dp[n - 2] :
                                  dp[n - 1]);
    }
     
    // driver code
    public static void main(String[] args)
    {
        int n = 4, k = 3, x = 2;
        System.out.println(countarray(n, k, x));
    }
}
 
 
// This code is contributed by rishabh_jain

# Python3 code to find count of arrays.
 
# Return the number of lists with
# given constraints.
def countarray( n , k , x ):
     
    dp = list()
     
    # Initialising dp[0] and dp[1]
    dp.append(0)
    dp.append(1)
     
    # Computing f(i) for each 2 <= i <= n.
    i = 2
    while i < n:
        dp.append( (k - 2) * dp[i - 1] +
                   (k - 1) * dp[i - 2])
        i = i + 1
     
    return ( (k - 1) * dp[n - 2] if x == 1 else dp[n - 1])
 
# Driven code
n = 4
k = 3
x = 2
print(countarray(n, k, x))
 
# This code is contributed by "Sharad_Bhardwaj".

// C# program to find count of arrays.
using System;
 
class GFG
{
// static int MAXN = 109;
 
    public static int countarray(int n, int k,
                                    int x)
    {
        int[] dp = new int[109];
 
        // Initialising dp[0] and dp[1].
        dp[0] = 0;
        dp[1] = 1;
 
        // Computing f(i) for each 2 <= i <= n.
        for (int i = 2; i < n; i++)
            dp[i] = (k - 2) * dp[i - 1] +
                    (k - 1) * dp[i - 2];
 
        return (x == 1 ? (k - 1) * dp[n - 2] :
                                   dp[n - 1]);
    }
     
    // Driver code
    public static void Main()
    {
        int n = 4, k = 3, x = 2;
        Console.WriteLine(countarray(n, k, x));
    }
}
 
 
// This code is contributed by vt_m

<?php
// PHP Program to find
// count of arrays.
 
$MAXN = 109;
 
// Return the number of arrays
// with given constartints.
function countarray($n, $k, $x)
{
    $dp = array( 0 );
 
    // Initialising dp[0] and dp[1].
    $dp[0] = 0;
    $dp[1] = 1;
 
    // Computing f(i) for
    // each 2 <= i <= n.
    for ( $i = 2; $i < $n; $i++)
        $dp[$i] = ($k - 2) * $dp[$i - 1] +
                  ($k - 1) * $dp[$i - 2];
 
    return ($x == 1 ? ($k - 1) *
            $dp[$n - 2] : $dp[$n - 1]);
}
 
// Driven Code
$n = 4; $k = 3; $x = 2;
echo countarray($n, $k, $x) ;
 
// This code is contributed by anuj_67.
?>

<script>
 
// Javascript program to find count of arrays.
let MAXN = 109;
   
function countarray(n, k, x)
{
    let dp = [];
 
    // Initialising dp[0] and dp[1].
    dp[0] = 0;
    dp[1] = 1;
 
    // Computing f(i) for each 2 <= i <= n.
    for(let i = 2; i < n; i++)
        dp[i] = (k - 2) * dp[i - 1] +
                (k - 1) * dp[i - 2];
 
    return (x == 1 ? (k - 1) * dp[n - 2] :
                               dp[n - 1]);
}
 
// Driver code
let n = 4, k = 3, x = 2;
 
document.write(countarray(n, k, x));
 
// This code is contributed by sanjoy_62
 
</script>

Producción : 

3