256. Paint House
Problem
Paint n houses with 3 colors so no two adjacent houses have the same color. Find the minimum cost.
There are n houses to be painted. Each house can be painted with one of 3 colors: Red, Blue, or Green. The cost of painting each house with each color is given in a 2D array costs where costs[i][j] is the cost of painting house i with color j.
No two adjacent houses can have the same color. Find the minimum cost to paint all houses.
Examples
Input: [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Input: [[7,6,2]]
Output: 2
Hints
Use DP: dp[i][j] = minimum cost to paint house i with color j.
For each house, dp[i][j] = costs[i][j] + min(dp[i-1][k]) where k != j.
Optimize to O(1) space by using only the previous row.
Related Problems
256. Paint House
Paint n houses with 3 colors so no two adjacent houses have the same color. Find the minimum cost.