Paint House II

You are a professional painter tasked with painting a row of houses. Each house can be painted with one of k colors. The cost of painting each house with a specific color varies. However, there's a crucial rule: no two adjacent houses can be painted with the same color. Your goal is to find the minimum total cost to paint all the houses while adhering to this rule.

Problem Description

Given a 2D array costs, where costs[i][j] represents the cost of painting house i with color j. There are n houses and k colors. You need to find the minimum cost to paint all n houses such that no two adjacent houses have the same color.

Input:

• costs: A 2D array of integers. costs[i][j] is the cost to paint house i with color j.
  • i ranges from 0 to n-1 (representing the houses).
  • j ranges from 0 to k-1 (representing the colors).

Output:

• An integer representing the minimum total cost to paint all houses.

Requirements:

1. Every house must be painted.
2. No two adjacent houses can have the same color.

Edge Cases to Consider:

• What if there's only one house (n=1)?
• What if there's only one color (k=1)? (This case might lead to an impossible scenario if n > 1).
• What if the costs array is empty?

Examples

Example 1:

Input: costs = [[17,2,17],[16,16,5],[14,3,19]]
Output: 10
Explanation:
Paint house 0 with color 1 (cost 2).
Paint house 1 with color 2 (cost 5).
Paint house 2 with color 1 (cost 3).
Total cost: 2 + 5 + 3 = 10.

Example 2:

Input: costs = [[1,5,3],[2,9,4]]
Output: 5
Explanation:
Paint house 0 with color 0 (cost 1).
Paint house 1 with color 2 (cost 4).
Total cost: 1 + 4 = 5.

Example 3:

Input: costs = [[1,2,3],[1,2,3],[1,2,3]]
Output: 6
Explanation:
Paint house 0 with color 0 (cost 1).
Paint house 1 with color 1 (cost 2).
Paint house 2 with color 0 (cost 1).
Total cost: 1 + 2 + 1 = 4.
(Alternative: Paint house 0 with color 0 (cost 1), house 1 with color 2 (cost 3), house 2 with color 0 (cost 1). Total cost: 1 + 3 + 1 = 5)
(Alternative: Paint house 0 with color 1 (cost 2), house 1 with color 0 (cost 1), house 2 with color 1 (cost 2). Total cost: 2 + 1 + 2 = 5)
(Alternative: Paint house 0 with color 2 (cost 3), house 1 with color 0 (cost 1), house 2 with color 1 (cost 2). Total cost: 3 + 1 + 2 = 6)
Minimum cost is 4.

Constraints

• 1 <= n <= 100 (number of houses)
• 1 <= k <= 20 (number of colors)
• 0 <= costs[i][j] <= 1000 (cost to paint a house with a specific color)
• costs will contain n rows and k columns.
• The problem expects an efficient solution, likely better than brute-force enumeration of all possibilities.

Notes

This problem can be approached using dynamic programming. Consider how the minimum cost to paint the current house depends on the minimum costs to paint the previous house. Be mindful of the constraint that adjacent houses cannot share the same color.

A common optimization for this type of problem involves efficiently tracking the minimum and second minimum costs from the previous row to help determine the current minimum.