count houses in a row, and count is even. Each house is painted one of three colours; prices[i][j] is the cost of painting house i in colour j + 1.
The street looks good when both rules hold:
- neighbouring houses have different colours;
- houses at the same distance from the two ends of the street (house i and house count - 1 - i) also have different colours.
Return the minimum cost of painting the street so that it looks good.count=2, prices=[[4, 1, 6], [2, 1, 9]] → 3
Both houses want colour 2, but they are neighbours (and a mirror pair). Best: house 0 in colour 2 (1), house 1 in colour 1 (2), total 3.
count=4, prices=[[1, 5, 5], [5, 1, 5], [1, 5, 5], [5, 1, 5]] → 4
Colours 1, 2, 1, 2 cost 4: neighbours differ, and so do the mirror pairs, with houses 0 and 3 in colours 1 and 2, and houses 1 and 2 in colours 2 and 1.
count=4, prices=[[1, 9, 9], [9, 1, 9], [9, 1, 9], [1, 9, 9]] → 20
Houses 1 and 2 are neighbours, so only one of them gets colour 2; houses 0 and 3 are a mirror pair, so only one of them gets colour 1.
count is evencount=2, prices=[[4, 1, 6], [2, 1, 9]]
3
Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.