NUHMAN.com

Introduction

LeetCode 256: Paint House is a dynamic programming problem that challenges you to minimize the cost of painting a row of houses such that no two adjacent houses have the same color.

It’s a classic example of applying bottom-up DP and commonly appears in interviews due to its real-world resemblance (like scheduling or constraint satisfaction).

Problem Statement

You are given a 2D array costs where costs[i][j] represents the cost of painting house i with color j. There are 3 colors: red (0), blue (1), and green (2).

You must paint all houses such that no two adjacent houses have the same color, and return the minimum total cost.

Example:

python

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

Step-by-Step Solution in Python

✅ Step 1: Understand the Goal

We want to paint all houses while:

• Minimizing the total cost
• Ensuring no two adjacent houses have the same color

✅ Step 2: Dynamic Programming Strategy

Let’s define:

• dp[i][j] = the minimum cost to paint up to house i with color j

Transition:

pgsql

dp[i][j] = costs[i][j] + min(dp[i-1][k]) where k ≠ j

We build up the cost bottom-up, choosing the best color for each house based on previous choices.

Step 3: Code It

python

def minCost(costs: list[list[int]]) -> int:
    if not costs:
        return 0

    n = len(costs)

    for i in range(1, n):
        # Update each color by adding the minimum cost of previous house with different color
        costs[i][0] += min(costs[i - 1][1], costs[i - 1][2])
        costs[i][1] += min(costs[i - 1][0], costs[i - 1][2])
        costs[i][2] += min(costs[i - 1][0], costs[i - 1][1])

    # The answer is the minimum cost to paint the last house
    return min(costs[-1])

Explanation of the Code

1. In-place DP update:
2. We reuse the input list costs as our DP table to save space.
3. Recurrence:
4. Each cost is updated by adding the minimum of the other two colors from the previous house.
5. Final result:
6. The minimum of the last row in costs gives us the total minimum cost.

Dry Run Example

Input: [[17,2,17],[16,16,5],[14,3,19]]

• After processing house 1:
• [17, 2, 17]
• [18, 33, 7]
• After processing house 2:
• [17, 2, 17]
• [18, 33, 7]
• [21, 10, 37]

Answer: min(21, 10, 37) = 10

Time and Space Complexity

• Time Complexity: O(n), where n = number of houses
• Space Complexity: O(1) (in-place modification of costs)

Conclusion

LeetCode 256 is a great example of dynamic programming applied to real-world constraints. It teaches:

• How to define subproblems (dp[i][j])
• Efficient in-place updates to reduce space
• Handling mutually exclusive choices (like colors or tasks)

This problem sets the foundation for more complex variants like:

• LeetCode 265: Paint House II with k colors