Is "house coloring with three colors" NP?

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.

The explanation by @Knoothe is spot-on, but I believe the implementation can be improved - it uses O(n) additional space for storing previous values, but we can do it in O(1) space by noticing that we only need the previous value for each color, not the whole array of values. Here's how:

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)

For example:

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