使用 k 个字符组成长度为 n 的字符串，使得最多两个相邻字符可以相同的方法数

Question

嗨，请告诉我我的循环关系有什么问题。

我的逻辑：

分配第一个 element=k 的方式数和 next (n-1) 元素不同的方式数 (k-1)*f(n-2)

和分配两个相同元素的方法数：k + (k-1)*f(n-1)

因此关系：

no. of ways = ∑(k + (k-1)*f(n-1) + k + (k-1)*f(n-1))

我可以看到一些错误，例如包含重复项，但是，我无法弄清楚它们之间的关系。

您还可以找到以下代码：

    def count_num_ways(n, k):
        dp = [0 for i in range(n+1)]

        dp[0] = 0
        dp[1] = k

        for i in range(2, n+1):
            dp[i] =  sum(
                [
                     k+( k-1 )*dp[n-2],
                     k+(k-1)*dp[n-1]-k
                ]
            )

        print(dp)

谢谢。

Answer 1

令f(n)等于最后两个字符相同的n个元素的构成方式数,

---+-+-+-+-+---+-+
...|a|a| | |...| |
---+-+-+-+-+---+-+
        \---v---/
            n
f(n) = number of ways to fill these n elements.

并令g(n)等于n个元素的构成方式数而最后两个字符不同.

---+-+-+-+-+---+-+
...|a|b| | |...| |
---+-+-+-+-+---+-+
        \---v---/
            n
g(n) = number of ways to fill these n elements.

与f(n)一样，由于最后两个字符相同，我们需要选择一个不同的字符，即(k-1)，最后两个字符将不同，即g(n-1) ，结果为：

f(n) = (k-1)*g(n-1)

与g(n)一样，由于最后两个字符不同，我们可以选择相同的字符或不同的字符。对于第一种情况，相同的字符是唯一的选择：1，最后两个字符相同：f(n-1)。对于第二种情况，不同的字符选项：(k-1)和不同的函数：g(n-1)，结果是：

g(n) = 1*f(n-1) + (k-1)*g(n-1)

第一个元素，我们选择一个字符k，答案是

k*g(n-1)

Ps:

实际上你可以用 f(n-1) 代入第二个等式，但我认为这样更直观。

代码

这里是一个例子Python代码

def f(n):
    if n == 0:
        return 1
    return (k-1)*g(n-1)


def g(n):
    if n == 0:
        return 1
    return f(n-1) + (k-1)*g(n-1)


n, k = 4, 2

print(k*g(n-1))

Answer 2

根据你的问题，我得出2个结论：

组成一个字符串时，同一字符可以使用任意次数。
k > 1 因为否则 n > 2.

在这种情况下，这是一个典型的组合问题，您可以使用简单的数学公式计算组合的数量。您需要考虑 2 种情况 - 所有相邻字符都不同，并且正好有 2 个相邻字符相同。

说明

情况 A - 所有相邻字符都不同

有 k 种方法可以选择字符串中的第一个字符。对于接下来的字符，总是有 k - 1 种方式（它们必须不同！）。因此，组合总数为k(k-1)^n-1.

情况 B - 2 个相邻字符相同

假设 2 个相同的字符是字符串的第一个和第二个字符。有 k 种方法可以创建这样的对，因为两个元素都相等！然后，对于字符串中的每个其他位置，有 k - 1 种选择字符的方法。

如果一对相同的元素在中间或末尾怎么办？好吧，组合的数量将保持不变 - 它始终是 k 种方式来选择字符串中的第一个元素，而 k - 1 种方式来选择其他元素。如果 2 个位置必须由相等的字符占据，那么和以前一样，有 k - 1 种设置方式。其中，固定对位置有k(k-1)^n-2

由于这样的位置数为n-1，所以组合数为(n-1)k(k-1)^n-2

结果

所以，总的组合数是k(k-1)^n-1 + (n-1)k(k-1)^{n -2}

Answer 3

注：我解释的字符位置是从1开始的，所以第一个字符在位置1，第二个字符在位置2，依此类推

让我们定义：

valid string：使用k个字符组成的字符串，最多两个相邻字符相同。
f(n):长度n的valid string个数和最后两个字符不同
g(n):长度n的valid string个数和最后两个字符相同
h(n)：长度n的valid string个数。

假设您已经为所有m <= n计算了f(m)和g(m)的值：让我们找到f(n+1)和g(n+1)。

让我们计算f(n+1):个valid string个长度n+1并且最后两个字符不同。根据每个 valid string 的长度 n 你发现：

如果最后两个字符不同，您有 k-1 种方法将字符放在 n+1 位置并形成长度 n+1 的 valid string ] 最后两个字符不同。
如果最后两个字符相同，您有 k-1 种方法将字符放在 n+1 位置并形成长度 [=32] 的 valid string =] 其中最后两个字符不同。

这两个选项显然是相互排斥的，因为长度为 n 的每个 valid string 的最后两个字符不能既相等又不同。此外，这两个选项足以帮助我们正确计算所有 valid string 的长度 n+1 其中最后两个字符不同，因为每个 valid string 的长度 n+1 其中最后两个characters are different 位置 n-1 和 n 处的字符不同或相同（以上两个选项）。

所以我们最后可以说：f(n+1) = (k-1) * f(n) + (k-1) * g(n)
|第一个选项 | |第二个选项|

让我们计算g(n+1):个valid string个长度n+1并且最后两个字符相同。根据每个 valid string 的长度 n 你发现：

如果最后两个字符不同，您只有一种方法可以将字符放在位置 n+1 并形成长度为 n+1 的 valid string，最后一个两个字符相同。
如果最后两个字符相同，您有 0 种方法将字符放在 n+1 位置并形成长度为 n+1 的 valid string，最后一个两个字符相同，因为一个 valid string 最多有两个相等的相邻字符。因此，如果 n+1 和 n 位置的字符相同，则最后 3 个字符相同。

再一次，这两个选项显然是相互排斥的，因为长度为 n 的每个 valid string 的最后两个字符不能既相等又不同。此外，这两个选项足以帮助我们正确计算所有 valid string 长度 n+1 其中最后两个字符相同，因为每个 valid string 长度 n+1 其中最后两个字符相同位置 n-1 和 n 的字符不同或相同（以上两个选项）。

所以我们最后可以说：g(n+1) = f(n)
|第一个选项 |

现在很容易看出：h(n) = f(n) + g(n) 因为长度为 n 的 valid string 的最后两个字符相等或不同。

给出该等式并将 g(n) 替换为它的值，我们有：h(n) = f(n) + f(n-1).

此外，考虑到 f(n) 和 g(n) 只需要 1 个前值才能正确计算，我们必须事先计算 f(1) 和 `g(1)``。

很容易看出：

f(1) = k
g(1) = 0

数学部分结束。编程部分开始:)

注意：所有的解决方案都是用python代码写的。

您有 3 种方法可以做到这一点，它们都以 O(n) 时间复杂度计算 h(n)，第三种以 O(log n) 时间复杂度计算 h(n)。让我们检查一下！

解决方案 #1：递归
时间复杂度：O(n)

对于解决方案 #1，让我们询问值并假设已经计算了先前的值（为此我们需要递归）。

def f(n, k):
    return k if n == 1 else (k - 1) * (f(n - 1, k) + g(n - 1, k))

def g(n, k):
    return 0 if n == 1 else f(n - 1, k)

def h(n, k):
    return f(n, k) + g(n, k)

解决方案 #2：迭代
时间复杂度：O(n)

对于解决方案 #2，让我们根据之前已经计算的值计算这些公式的下一个值。

def h(n, k):
    fn, gn = k, 0
    for _ in range(n):
        hn = fn + gn
        fn, gn = (k - 1) * (fn + gn), fn
    return hn

解决方案 #3：Matrix Exponentiation and Binary Exponentiation
时间复杂度：O(log n)

给定 h(n) = f(n) + g(n) 和 g(n) = f(n-1) 然后 h(n) = f(n) + f(n-1)。
此外，给定 f(n) = (k-1) * f(n-1) + (k-1) * g(n-1) 和 g(n) = f(n-1)
然后 f(n) = (k-1) * f(n-1) + (k-1) * f(n-2).

因此，使用下面的矩阵和向量并假设 f(0) = 0，我们可以正确计算 h(n)，如下所示：

| k - 1      k - 1 |^(n-1)   *   | f(n-1) |   =   | f(n)   |
|   1          0   |             | f(n-2) |       | f(n-1) |

代码：

def h(n, k):
    def _matrix_multiplication(matrix_a, matrix_b):
        result = [ [ 0 ] * len(matrix_b[ 0 ]) for _ in range(len(matrix_a)) ]
        for i in range(len(result)):
            for j in range(len(result[ 0 ])):
                for k in range(len(matrix_a[ 0 ])):
                    result[ i ][ j ] += matrix_a[ i ][ k ] * matrix_b[ k ][ j ]
        return result

    def _binary_exponentiation(matrix, n):
        result = [
            [ 1, 0 ],
            [ 0, 1 ]
        ]
        while n != 0:
            if n % 2 == 1:
                result = _matrix_multiplication(result, matrix)
            n //= 2
            matrix = _matrix_multiplication(matrix, matrix)
        return result

    matrix = [
        [ k - 1, k - 1 ],
        [ 1, 0 ]
    ]

    matrix = _binary_exponentiation(matrix, n - 1)
    vector1 = [ [ k ], [ 0 ] ]
    vector2 = _matrix_multiplication(matrix, vector1)
    return sum(row[ 0 ] for row in vector2)

希望这 3 个解决方案中的任何一个对您有所帮助！

使用 k 个字符组成长度为 n 的字符串，使得最多两个相邻字符可以相同的方法数

Number of ways to form a string of length n using k characters such that at most two adjacent characters can be same

python

algorithm

dynamic-programming

combinatorics

Ps:

代码

说明

情况 A - 所有相邻字符都不同

情况 B - 2 个相邻字符相同

结果