Paint House

How it works

Looking at the bottom-up solution, we notice that computing the DP values for house i only requires the values from house i-1. We do not need to keep track of all previous houses.

This means we can reduce space from O(n) to O(1) by only storing the costs for the previous house. We maintain three variables representing the minimum costs ending with each color and update them as we process each house.

Steps

1. Initialize three variables dp0, dp1, dp2 to 0, representing the minimum cost to reach the current position ending with each color.
2. For each house, compute new values for all three colors simultaneously. For each color, add the current cost to the minimum of the other two previous costs.
3. Update all three variables at once to avoid using stale values.
4. Return the minimum of the three final values.

Complexity

• Time complexity: O(n)
• Space complexity: O(1) extra space.

Things to watch for

Forgetting the Adjacent Constraint

A common mistake is to simply pick the minimum cost color for each house independently. This greedy approach ignores the constraint that adjacent houses cannot have the same color. The solution must ensure that each house is painted with a different color than the previous house.

Updating DP Values In-Place Incorrectly

When using the space-optimized approach, updating dp0, dp1, and dp2 sequentially causes bugs because you overwrite values that are still needed for subsequent calculations. All three new values must be computed using the old values before any of them are updated. Use temporary variables or compute all new values simultaneously.

Off-By-One Errors in Memoization Index

When using memoization with prevColor = -1 to indicate no previous constraint, forgetting to offset the index by 1 when accessing the cache leads to array index out of bounds errors. The cache needs to handle prevColor values from -1 to 2, requiring an offset or an extra dimension.

from typing import List

class Solution:
    def minCost(self, costs: List[List[int]]) -> int:
        dp = [0, 0, 0]

        for i in range(len(costs)):
            dp0 = costs[i][0] + min(dp[1], dp[2])
            dp1 = costs[i][1] + min(dp[0], dp[2])
            dp2 = costs[i][2] + min(dp[0], dp[1])
            dp = [dp0, dp1, dp2]

        return min(dp)

class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int dp0 = 0, dp1 = 0, dp2 = 0;

        for (const auto& cost : costs) {
            int newDp0 = cost[0] + min(dp1, dp2);
            int newDp1 = cost[1] + min(dp0, dp2);
            int newDp2 = cost[2] + min(dp0, dp1);
            dp0 = newDp0;
            dp1 = newDp1;
            dp2 = newDp2;
        }

        return min({dp0, dp1, dp2});
    }
};