House painting minimum cost

A row of houses must each be painted one of k colors. costs[i][j] is the cost to paint house i with color j. No two adjacent houses may share a color. Return the minimum total cost to paint all houses. costs has at least one color column when non-empty; it may be empty.