algorithm - 如何找到选择 3 种类型的 k 个对象的方法数

Question

给你一个整数 k和 3 种类型的对象 - A、B 和 C，每种类型都有大量对象。你可以用多少种方式安排k对象，以便您可以任意次数地选择任何类型的对象，但有一个限制，即 B 始终介于 A 和 C 或 C 和 A 之间。

例如，如果 k 为 3，则答案为:10解释:{AAA, AAC, ABC, ACA, ACC, CAA, CAC, CBA, CCA, CCC}

我尝试使用动态规划来解决它，但我不知道这是否是正确的方法。

我试过这样的事情:f(n) = 2*f(n-1) + f(n-2) ，在这里你需要一个大小为 k 的数组和 f(1) = 2 {A, C}和 f(2) = 4 {AA, AC, CA, CC} ,

因此，如果第 (n-1) 个字母是 A 或 C，则第 n 个字母可以是 A 或 C，但如果是 B，则第 n 个字母只能是互补的 aplphabet 即，如果第 (n-2) 个字母是A，则第 n 个字母为 C，反之亦然。但我觉得我遗漏了一些案例。

有没有更好的方法，有人可以帮我解决这个问题吗？

Answer 1

令 L 为此类字符串的语言，La 和 Lc 为字符串分别以 A 或 C 结尾的语言的子集。

然后我们可以写出这个无歧义的语法:

L = La | Lc
La = "A" | L + "A" | Lc + "BA"
Lc = "C" | L + "C" | La + "BC"

令 L(n)、La(n)、Lc(n) 分别为三种语言中长度为 n 的字符串的数量。根据对称性，La(n) = Lc(n) = L(n)/2。

然后，根据第二个等式并利用文法明确的事实，对于 n > 1，La(n) = L(n-1) + Lc(n-2)，代入我们得到:L( n) = 2L(n-1) + L(n-2)。我们有 L(0)=0 和 L(1)=2。

为了计算 L，我们可以编写迭代代码(您可以称之为动态规划):

def L(n):
    a, b = 0, 2
    for _ in xrange(n):
        a, b = b, a + 2 * b
    return a

或者，就像我们对斐波那契数列所做的那样，我们可以使用矩阵求幂来解决它，这可以在 O(log n) 算术运算中完成。

L(n) = the first component of [0 1]^n (0)
                              [1 2]   (2)