动态规划：给一排的房子外墙涂色

Question

7.现给一排栋房子的外墙涂色，共有种颜色可以使用。为了美观，要求每栋房子和它相邻的房子具有不同的颜色，并且任意连续4栋房子至少包含3种颜色。求一共有多少种涂色方案。
测试样例是 输入4，3 返回18
请问一下该怎么写？知道应该是用动规，但具体不会用，希望能得到指点！谢谢！

Answer 1

m0_67966140 上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

这个问题可以使用动态规划来解决。下面是一种可能的解决方案：

1. 定义状态：将每栋房子的涂色方案作为状态。假设f(i, j)表示前i栋房子涂色方案中，第i栋房子颜色为j的涂色方案总数。

2. 初始化状态：对于第一栋房子，每种颜色的涂色方案数都是1。即f(1, j) = 1 (1 ≤ j ≤ n)。

3. 状态转移方程：对于第i栋房子，可以选择与前一栋房子有不同颜色的颜色涂色。如果第i栋房子颜色与前一栋房子颜色相同，则不符合美观要求；如果前一栋房子和第i-1栋房子的颜色相同，前一栋房子和第i-2栋房子的颜色也相同，则不符合连续4栋房子至少包含3种颜色的要求。

   f(i, j) = Σ {f(i-1, k)} (1 ≤ k ≤ n and k ≠ j and j ≠ i-1 and k ≠ i-2)

4. 计算结果：最终的结果是所有状态f(N, j)相加，这里N表示房子的总数。

通过以上动态规划的解决方案，可以求得给定房子外墙涂色的方案总数。具体实现时，可以使用二维数组来保存状态，并使用循环计算每个状态的值。

以下是一个简单的实现示例（使用Python语言）：

def paintHouse(n, m):
    dp = [[0] * (m+1) for _ in range(n+1)]

    # 初始化状态
    for j in range(1, m+1):
        dp[1][j] = 1

    # 计算状态
    for i in range(2, n+1):
        for j in range(1, m+1):
            for k in range(1, m+1):
                if k != j and k != i-1 and j != i-2:
                    dp[i][j] += dp[i-1][k]

    # 计算结果
    result = sum(dp[n])
    return result

n = 7  # 房子的总数
m = 6  # 颜色的总数
result = paintHouse(n, m)
print("涂色方案总数：", result)

在以上示例中，我们定义了一个dp二维数组来保存状态，并使用三层循环来计算每个状态的值。最终求和dp[N]的值即为总的涂色方案数。