229. Paint House
A street has n houses in a row, and each must be painted red, green, or blue — with the rule that no two neighboring houses share a color.
You are given costs, an n × 3 matrix where costs[i][0], costs[i][1], and costs[i][2] are the prices of painting house i red, green, and blue respectively. Return the minimum total amount needed to paint every house under the rule.
Example 1:
Input: costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]
Output: 10
Explanation: Paint house 0 green (2), house 1 blue (5), house 2 green (3): 2 + 5 + 3 = 10, and no neighbors match.
Example 2:
Input: costs = [[7, 6, 2]]
Output: 2
Explanation: One house has no neighbors — just take its cheapest color, blue at 2.
Constraints:
- 1 ≤ n ≤ 100
- 0 ≤ costs[i][j] ≤ 10⁴
Hints:
Greedy fails: taking each house's cheapest color can force an expensive clash later. The choice at house i only interacts with house i−1's color.
Define best(i, c) = cheapest way to paint houses 0..i with house i colored c. It depends only on best(i−1, ·) for the two other colors.
Carry just three running totals — cheapest schedule ending in red, green, or blue — and update them per house for O(1) extra space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: costs = [[17, 2, 17], [16, 16, 5], [14, 3, 19]]
Expected output: 10