Interview Notes Search

This page uses the site's newer layout, so only the problem statement and the section outline survive in the public payload — open the original for the rest.

Dynamic Programming

Paint House II

hard

DESCRIPTION (inspired by Leetcode.com)

You are a renowned painter who is given a task to paint n houses in a row. This time, you have k colors available. The cost of painting each house with each color is different and given in a 2D array costs:

  • costs[i][j] = cost of painting house i with color j

No two neighboring houses can have the same color. Return the minimum cost to paint all houses.

Constraints:

  • 0 ≤ n ≤ 100

  • 1 ≤ k ≤ 20

  • costs[i].length == k

  • 1 ≤ costs[i][j] ≤ 1000

Follow-up: Can you solve this in O(n × k) time instead of the naive O(n × k²)?

Example 1

Input:

costs = [[4, 2, 8], [7, 1, 5], [3, 9, 6]]

Output:

8

Explanation:

  • House 0: Color 0 (cost = 4)

  • House 1: Color 1 (cost = 1)

  • House 2: Color 0 (cost = 3)

  • Total = 4 + 1 + 3 = 8

Example 2

Input:

costs = [[8, 3, 12, 5], [15, 9, 4, 7]]

Output:

7

Explanation: Paint house 0 with color 1 (cost = 3), house 1 with color 2 (cost = 4). Total = 7.

Explanation

Building Intuition

Approach 1: Direct Extension of Paint House

The Key Insight

Approach 2: Optimized DP with Min Tracking

Walkthrough

Solution

Can We Get O(1) Space Like Paint House?