algorithm - 我该如何处理这个 Combinatorics Fence-Paint 算法？

Question

我在 lintcode 上遇到了这个问题，我已经阅读了两个过去的解决方案，但它们对我来说都没有意义。

问题如下:

There is a fence with n posts, each post can be painted with one of the k colors.
You have to paint all the posts such that no more than two adjacent fence posts have the same color.
Return the total number of ways you can paint the fence.

给定 n =3，k=2，返回 6。

所以我理解的部分是，如果 n=0(我们有 0 个帖子)或 k = 0(我们有 0 个绘画)，我们无法绘画任何东西，所以返回 0

如果 n == 1，帖子可以用 K 种方式绘制，所以返回 k

当 n 为 2 时，如果相邻的帖子相等，我们可以用 K*1 种方式绘制，如果相邻的帖子不同，我们可以用 K*(K-1) 种方式绘制。

如果 n ==3 或更多:相同的相邻颜色将是:K * 1 * K-1 * 1 * K-1 ...不同的是:K * K-1 * K-1 ....

我该如何从这里开始？我见过一个人再次用 [0、k、2k 和 0] 创建一个矩阵，另一个人将“不同颜色”简化为 (k+k*(k-1)) * (k-1) 但我不知道他们中的任何一个是如何跳到他们结论的那一步

编辑:一个人的解决方案如下:

class Solution:
# @param {int} n non-negative integer, n posts
# @param {int} k non-negative integer, k colors
# @return {int} an integer, the total number of ways
def numWays(self, n, k):
    # Write your code here
    table = [0, k, k*k, 0]

    if n <= 2:
        return table[n]

    # recurrence equation
    # table[posts] = (color - 1) * (table[posts - 1] + table[posts - 2])
    for i in range(3, n + 1):
        table[3] = (k - 1) * (table[1] + table[2])
        table[1], table[2] = table[2], table[3]

    return table[3]

但我不明白为什么他的表末尾有[0]，以及他如何建立递推方程

Answer 1

这个问题最困难的部分是设置递归。令 L 为返回给定 n 个帖子和 k 种颜色的组合数的函数。那么有两种情况需要考虑:

一个。添加两个相同颜色的帖子:

L(n+2,k) = (k-1)*L(n,k)

添加两个不同颜色的帖子:

L(n+1,k) = (k-1)*L(n,k)

它给出了公式:

L(n,k) = (k-1)*(L(n-1,k)+L(n-2,k))

示例

对于 n=3 和 k=2，假设我们知道前两个帖子的组合数是

n=1 | k = 2

n=2 | k*k = 4

现在要求解 n=3，我们需要使用先前计算的具有相邻 n=2 和 n=3 的值

一个。不同的颜色:通过添加一个不同于尾随的帖子，sum[2]*(k-1) = 4

相同颜色:后退一个图 block 并添加两个颜色相同但 n=1 的图 block ，得到 sum[1]*(k-1) = 2

至于矩阵，这是个人喜好问题，current 和 prev 之类的变量也可以。