Paint House

Problem Paint n houses with red/blue/green given an n x 3 cost matrix; adjacent houses must differ in color. Minimize total cost.

Input / Output

• Input: int costs[n][3]. Output: min total cost.

Constraints

• n up to 100 (classic); O(n) with O(1) state expected.

Example

• [[17,2,17],[16,16,5],[14,3,19]] → 10 (blue 2, green 5, blue 3).

Expected approach

• DP over colors: best[i][c] = costs[i][c] + min(best[i−1][other two]); answer = min of last row; roll to three variables → O(n) time O(1) space. Escalation — Paint House II (k colors): naive O(n·k^2) → O(n·k) by tracking the min and second-min of the previous row (use second-min when the color matches the min's color). The min/second-min trick is what SDE-level probing targets. Fence-painting (same color allowed ≤2 in a row) is the adjacent variant.