No, it is not NP-hard (technically, "NP-complete" is the wrong term for this, as this is not a decision problem).
Dynamic programming works, and gives you an O(n) time algorithm. (n is the number of houses).
You maintain three arrays R[1..n], B[1..n], G[1..n]
, where R[i]
is the minimum cost of painting houses 1, 2, 3 ... i
such that i
is colored Red. Similarly B[i]
is min cost of painting 1, 2 ... i
with i
being colored Blue, and G[i]
is with i
being colored Green.
You can compute R[i+1]
:
R[i+1]= (Cost of painting house i+1 Red) + minimum {G[i], B[i]}
.
Similarly B[i+1]
and G[i+1]
can be computed.
Ultimately you take the minimum of R[n], B[n] and G[n]
.
This is O(n) time and O(n) space.
For example consider the following cost matrix for the houses:
House #: 1 2 3 R : 1 4 6 G : 2 100 2 B : 3 100 4
The algorithm is building the following matrix to get the answer:
Houses : 0 1 2 3 R : 0 1 6 107 G : 0 2 101 8 B : 0 3 101 10
From the last column, where all 3 houses are painted, we can find the minimum cost, which is equal to 8 and corresponds to the combination [Green (2), Red (4), Green (2)].
Quick Python:
# rc = costs of painting red, bc of blue and gc of green.
def min_paint(rc, bc, gc):
n, i = len(rc), 1
r, b, g = [0]*n, [0]*n, [0]*n
r[0], b[0], g[0] = rc[0], bc[0], gc[0]
while i < n:
r[i] = rc[i] + min(b[i-1], g[i-1])
b[i] = bc[i] + min(r[i-1], g[i-1])
g[i] = gc[i] + min(b[i-1], r[i-1])
i += 1
return min(r, b, g)
def main():
print min_paint([1, 4, 6], [2, 100, 2], [3, 100, 4])
if __name__ == "__main__":
main()
The output will be ([1, 6, 107], [2, 101, 8], [3, 101, 10]), which is a cost matrix leading to the solution.