仅使用 3 个元素形成数组的方法数？

Question

我们需要找出可以形成仅包含 3 个元素（1,2 和 3）的 N 长度数组 (A) 的方法数。

数组的相邻元素如何放置在数组中几乎没有限制：

(A[i], A[i + 1])某种类型的相邻元素对的数量不能超过问题陈述中给出的数量。

example :

1, 2 : 2 (we can have at most 2 adjacent-pairs of value [1, 2] in the array)
1, 3 : 3
2, 1 : 1
2, 3 : 0 (we cannot have any adjacent-pairs of value [2, 3] in entire array)
3, 1 : 4
3, 2 : 3

对于 type 的相邻元素 A[i] == A[i + 1]，它们可以在数组中出现任意次数

1, 1 : inf
2, 2 : inf
3, 3 : inf

示例案例：

输入：

N = 3

1, 2 : 1 
1, 3 : 1
2, 1 : 1
2, 3 : 0 
3, 1 : 0
3, 2 : 0   

输出 ：

12

解释 ：

[1, 2, 1] , here { (1,2) : 1, (2,1) : 1 }, so valid 
[1, 2, 2]
[1, 1, 2]
[2, 1, 2]

[1, 3, 3] , here { (1,3) : 1, (3,3) : 1 }, so valid 
[1, 1, 3]
[2, 1, 3] , here { (2,1) : 1, (1,3) : 1 }, so valid 

[2, 1, 1] , here { (2,1) : 1, (1,1) : 1 }, so valid 
[2, 2, 1]     

[1, 1, 1] , here { (1,1) : 2 }, so valid, as adj-pairs (x, x) can be any number of times.
[2, 2, 2]
[3, 3, 3]

All other combinations of 1,2,3 are invalid like :
[3, 1, 1], [2, 3, 1], etc.

约束

1 <= N <= 10^6

0 <= limit[i][j] <= 10^5

where N = array length and limit[i][j] = number of pairs of type (i, j)

伪代码：

main() :
   ways = 0;
   for(p = 1; p <= 3; p++) :
       ways += num_ways(p, 1, n, A, limit);
   return ways;


num_ways(prev, i, n, A[], limit[][]) :
  
  if(i == n) return 1;
  
  ways = 0;
  for(e = 1; e <= 3; e++):
      if(limit[prev][e] > 0) 
          limit[prev][e] -= 1;
          ways += num_ways(e, i + 1, A, limit);
          limit[prev][e] += 1;

  return ways;

, where limit[i][j] means max number of adjacent-pairs of value (i, j) that can be present in array

伪代码解释：

我试图解决这个使用递归（蛮力），即在每个函数调用插入任何元素(1,2,3)的索引i，并检查是否(A[i - 1], A[i])对没有超过限制按在问题陈述给出的，如果是那么return别的继续调用 func()时i != n。

这种方法很好，但它给出了 TLE（超出时间限制）错误，因此它不是找出形成数组的方法数量的最佳方法。

有没有其他有效的方法来解决这个问题？

Answer 1

我采取的方法不是创建实际的数组。相反，我会通过分析你的限制来解决这个问题。

1, 2 : 2
1, 3 : 3
2, 1 : 1
2, 3 : 0
3, 1 : 4
3, 2 : 3

因此，您的系统中只允许有限数量的转换。

因此，我的出发点是计算所有可能的转换组合，并与每个组合的最小长度 n 相关联。这可以使用一些强力方法来执行，尽管可能存在也可能没有更有效的方法。

蛮力方法的输出示例应如下所示......

• 最小长度 2 次转换：

1, 2
1, 3
2, 1
3, 1
3, 2
So, n-2 pattern count = 5.

• 最小长度 3 个转换：

1, 2, 1
1, 3, 1
1, 3, 2
2, 1, 2
2, 1, 3
3, 1, 2
3, 1, 3
3, 2, 1
So, n-3 pattern count = 8.

一旦我们计算了每个最小长度的所有可能的组合计数，我们就根据实际输入 n 执行排列数学。我们可以重用我们创建的原始结构来非常快速地执行 n 的多个输入的计算。

例如，当 n = 3 时，我们从 3 开始进行空转换。然后我们添加 8，以实现不需要最小长度 n 的转换的排列。然后我们计算最小长度 n - 1、n - 2 等的排列，直到 n - x = 2。排列是通过用多余空间移动每个转换的位置来计算的。即，其中 n = 3 且 min-n = 2，多余空间 = 1，因此我们可以将过渡向左/右移动 1，从而给我们 2 个模式而不是 1 个。因此，由于有 5 个长度为 2 的模式，并且每个都可以转换为 2 个模式，这样我们就有 10 个模式。所以我们有 10 + 8 + 3 = 21。

为了进一步阐明数学原理，我将在 n-3 模式上使用 n = 10。我们有 9 个转换槽和 2 个转换，可以应用排列数学：

1. 第一个转换可能发生在 9 个转换时隙中的前 8 个中的任何位置。选择哪个槽位决定了第二个转换可能进行的位置，但现在让我们忽略它。那么这就变成了 9!/7!。然而，这包括所有无序组合，因此我们希望将其进一步除以 2！。所以我们有 9 * 4 = 36 种组合，* n-3 种模式的模式计数 = 36 * 8。将其添加到 n-2 种模式、n-4 种模式等...

这可以概括为：

• sum(i: n ... 1) { patternCount(i) * ((n - 1)!)/(n - i - 1)!/i! }