“房子三色”是NP吗？

Question

考虑一下here描述的问题(如下所示)。一些更广为人知的NP-complete问题可以归结为它吗？

问题是：

有一排房子。每所房子都可以刷成三种颜色:红色、蓝色和绿色。用某种颜色粉刷每所房子的成本是不同的。你必须粉刷所有的房子，这样相邻的两座房子就不会有相同的颜色。你必须以最低的成本粉刷房子。你会怎么做？

注:将房子1刷成红色的成本与将房子2刷成红色的成本不同。每一种房子和颜色的组合都有它自己的成本。

Answer 1

@Knoothe的解释恰到好处，但我相信它的实现可以改进-它使用O(n)额外的空间来存储以前的值，但我们可以在O(1)空间中做到这一点，注意我们只需要每种颜色的前一个值，而不是整个值数组。下面是操作步骤：

def min_paint(rc, bc, gc):
    # `r` is the min cost of painting the current house
    # using color red; similarly for `b` and `g`
    r, b, g = 0, 0, 0
    for cr, cb, cg in zip(rc, bc, gc):
        # new value for `r` is current cost for `r` plus the
        # minimum cost for painting the previous house in one
        # of the other two colors; similarly for `b` and `g`
        r, b, g = cr + min(b, g), cb + min(r, g), cg + min(r, b)
    # answer is the min cost for painting the last house
    return min(r, b, g)

例如：

min_paint([1, 4, 6], [2, 100, 2], [3, 100, 4])
=> 8