计算具有不同值的连续元素的数组数量

给定三个正整数 n、k 和 x。我们的任务是统计可以组成多少种大小为 n 的不同数组，使得每个元素的值在 1 到 k 之间，且任意两个相邻元素的值都不相同。此外，每个数组的首尾元素必须分别为 1 和 x。

示例：

**输入**：n = 4, k = 3, x = 2
**输出**：3

!image

我们使用动态规划和组合数学的思路来解决这个问题。

首先，大家可能会注意到，对于所有从 2 到 k 的 x，答案是相同的。这很容易证明，这一点在后面会非常有用。

让我们定义一个状态 f(i)，表示填充数组 A 的区间 [1, i] 的方案数，其中 A1 = 1 且 Ai ≠ 1。

因此，如果 x ≠ 1，问题的答案就是 f(n)/(k – 1)。因为 f(n) 是 An 填入 2 到 k 中任意数字的方案总数，而对于所有可能的 An 值，其对应的方案数都是相等的，所以针对某一个特定值的答案就是 f(n)/(k – 1)。

否则，如果 x = 1，答案就是 f(n – 1)。因为此时 An – 1 ≠ 1，而我们唯一可以填入 An 的数字就是 x = 1。

现在，主要的问题是如何计算 f(i)。让我们考虑 Ai – 1 可能的所有取值。我们知道它必须在 [1, k] 范围内。

• 如果 Ai – 1 ≠ 1，那么填充数组其余部分就有 (k – 2)f(i – 1) 种方式。因为 Ai 不能是 1 也不能是 Ai – 1（所以我们乘以 (k – 2)），而对于区间 [1, i – 1]，根据递归定义，有 f(i – 1) 种方式。
• 如果 Ai – 1 = 1，那么填充数组其余部分就有 (k – 1)f(i – 2) 种方式。因为 Ai – 1 = 1 意味着 Ai – 2 ≠ 1，这说明填充区间 [1, i – 2] 有 f(i – 2) 种方式，而 Ai 不能是 1，所以我们有 (k – 1) 种选择。

结合以上两种情况，我们得到：

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

这将帮助我们利用 f(i) 进行动态规划求解。

下面是这种方法的实现：

C++

// CPP Program to find count of arrays.
#include 
#define MAXN 109
using namespace std;

// Return the number of arrays with given constraints.
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

// 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

# 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#

// 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

JavaScript

“`javascript

// Javascript program to find count of arrays.

let MAXN = 109;

function countarray(n, k, x)

{

let