Paint House I, II

XXX. Paint House

Dynamic Programming

Problem Statement:

You are given an array costs where costs[i] contains the cost of painting house i in one of three colors: red, blue, or green. Each color is represented as costs[i][0], costs[i][1], and costs[i][2]. You need to paint all the houses such that no two adjacent houses have the same color and minimize the total cost.

Additionally, for a variant with k colors, each house can be painted in any of k colors represented in the costs matrix. The same constraint applies: no two adjacent houses can have the same color.

Algorithm:

Solution 1: Three Colors

This approach uses dynamic programming to keep track of the minimum cost of painting each house in red, green, or blue, while ensuring no two adjacent houses share the same color.

1. Initialize the costs for the first house with costs[0][0], costs[0][1], and costs[0][2].
2. Iterate through the rest of the houses, calculating the cost of painting each house in each color by adding the current cost to the minimum of the costs of the other two colors from the previous house.
3. At the end, return the minimum of the three costs from the last house.

Solution 2: K Colors

For the case where each house can be painted with any of k colors, we extend the logic to find the two smallest costs from the previous house:

1. Maintain two variables, min1 and min2, to track the smallest and second smallest costs from the previous house, along with their indices.
2. For each house, calculate the cost of painting it in each color, adding min1 unless it corresponds to the same color, in which case min2 is used.
3. Update min1, min2, and the index of min1 for the current house.
4. At the end, return min1, which contains the minimum cost for painting all houses.

Complexity:

Solution 1:
Time Complexity: O(n), where n is the number of houses.
Space Complexity: O(1), as no additional space is used beyond variables.

Solution 2:
Time Complexity: O(n * k), where n is the number of houses and k is the number of colors.
Space Complexity: O(1).

Java Implementation:

class Solution {
    // Solution 1: Three Colors
    public int minCost(int[][] costs) {
        if (costs.length == 0) return 0; // If no houses, cost is 0.

        // Initialize costs for the first house.
        int lastR = costs[0][0], lastG = costs[0][1], lastB = costs[0][2];

        // Iterate through the rest of the houses.
        for (int i = 1; i < costs.length; i++) {
            // Calculate the cost of painting the current house in red, green, and blue.
            int curR = Math.min(lastG, lastB) + costs[i][0];
            int curG = Math.min(lastR, lastB) + costs[i][1];
            int curB = Math.min(lastR, lastG) + costs[i][2];

            // Update the costs for the next iteration.
            lastR = curR; lastG = curG; lastB = curB;
        }

        // Return the minimum of the three costs from the last house.
        return Math.min(Math.min(lastR, lastG), lastB);
    }

    // Solution 2: K Colors
    public int minCostII(int[][] costs) {
        if (costs.length == 0) return 0; // If no houses, cost is 0.

        int min1 = 0, min2 = 0, mIndex = -1; // Track smallest costs and their index.

        // Iterate through each house.
        for (int i = 0; i < costs.length; i++) {
            int m1 = Integer.MAX_VALUE, m2 = Integer.MAX_VALUE, idx1 = -1;

            // Calculate costs for painting the current house with each color.
            for (int j = 0; j < costs[0].length; j++) {
                int cost = costs[i][j] + (j != mIndex ? min1 : min2); // Use min1 or min2.

                // Update smallest and second smallest costs.
                if (cost < m1) {
                    m2 = m1; m1 = cost; idx1 = j;
                } else if (cost < m2) {
                    m2 = cost;
                }
            }

            // Update min1, min2, and mIndex for the next house.
            min1 = m1; min2 = m2; mIndex = idx1;
        }

        return min1; // Return the minimum cost.
    }
}