265. Paint House II
Problem
Paint n houses with k colors so no two adjacent houses have the same color. Find the minimum total cost.
There are n houses to be painted. Each house can be painted with one of k colors. 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: [[1,5,3],[2,9,4]]
Output: 5
Input: [[1,3],[2,4]]
Output: 5
Hints
Use DP similar to Paint House, but track top two minimum colors for each house.
For each color j, find the minimum cost using a color that's not j from previous house.
Maintain two smallest values and their colors for optimization.
Related Problems
265. Paint House II
Paint n houses with k colors so no two adjacent houses have the same color. Find the minimum total cost.