Paint House

class Solution {
public:
    int calculateMinCost(vector<vector<int>>& expenses) {
        if (expenses.empty()) return 0;

        vector<int> lastRow = expenses.back();

        for (int i = expenses.size() - 2; i >= 0; --i) {
            vector<int> currentSpending = expenses[i];

            currentSpending[0] += min(lastRow[1], lastRow[2]);
            currentSpending[1] += min(lastRow[0], lastRow[2]);
            currentSpending[2] += min(lastRow[0], lastRow[1]);

            lastRow = currentSpending;
        }

        return min({lastRow[0], lastRow[1], lastRow[2]});
    }
};

The provided C++ class, Solution, includes a method named calculateMinCost designed to solve the problem of minimizing the painting cost of a series of houses, where each house can be painted with one of three different colors, and each color incurs a specific expense. The constraints specify that no two adjacent houses can be painted the same color.

The method takes a 2D vector expenses, where each row represents a house and the columns represent the cost of painting that house with one of the three colors. Here’s a breakdown of how the solution works:

1. Begin by checking if the expenses vector is empty. If it is, return 0, as there are no expenses to consider.
2. Initialize lastRow to the last row of the expenses vector, which represents the base case for the last house.
3. Iterate over the expenses from the second-to-last row up to the first row:
   • For each house (row), retrieve the current row’s expenses.
   • Update the expense of painting the house with each color by adding the minimum of the feasible expenses of painting the next house (from lastRow) with the other two colors. This step ensures that no two adjacent houses will have the same color and seeks to find the minimum expense to the current point.
   • Update lastRow to be the current row’s modified expenses for use in the next iteration.
4. After finishing the iteration for all houses, find the minimum expense from lastRow, which now contains the minimum accessible expenses for painting all houses up to that point.
5. Return the minimum value found, which provides the minimal cost of painting all the houses according to the given constraints.

Effectively, this code applies a dynamic programming approach that iteratively computes the minimal costs from the last house to the first, leveraging the computed results of subsequent houses to determine optimal solutions for preceding ones. This optimizes computation and adheres to the requirement of different colors for adjacent houses.

class Solution {
    public int calculateMinimalCost(int[][] paintingCosts) {
        if (paintingCosts.length == 0) return 0;

        int[] lastRow = paintingCosts[paintingCosts.length - 1];

        for (int i = paintingCosts.length - 2; i >= 0; i--) {
            int[] current = paintingCosts[i];

            current[0] += Math.min(lastRow[1], lastRow[2]);
            current[1] += Math.min(lastRow[0], lastRow[2]);
            current[2] += Math.min(lastRow[0], lastRow[1]);

            lastRow = current;
        }

        return Math.min(
            Math.min(lastRow[0], lastRow[1]),
            lastRow[2]
        );
    }
}

The provided Java solution addresses the "Paint House" problem, where the goal is to find the minimum painting cost for a row of houses such that no two adjacent houses have the same color. The solution uses dynamic programming to efficiently compute the minimal cost.

• Input: A 2D integer array paintingCosts, where paintingCosts[i][j] represents the cost of painting the i-th house with color j.
• Output: The method calculateMinimalCost returns the minimal cost of painting all houses under the given constraints.

Working:

1. First, check if the input array is empty. If empty, return 0 since no cost is associated with painting zero houses.
2. Initialize lastRow to hold the painting costs of the last row (or the last house) in the input array.
3. Iterate backwards through the array starting from the second-last row:
   • For each house (current), update its painting cost for each color by adding the minimum cost of painting the next house with the other two colors. This ensures no two adjacent houses are painted the same color.
   • Update lastRow to the current to use it for the next iteration in computing costs for the house before it.
4. After processing all rows (houses), determine the minimum cost from the first row of the array, which now contains the accumulative cost of painting all subsequent houses.
5. Return the minimum value among the three color options for the first house.

This method efficiently calculates the minimum painting cost using a bottom-up approach, ensuring each house is considered with optimal previous choices.