Untitled

import java.util.HashMap;
import java.util.Map;

public class PaintHouse {
    public static int minCost(int[][] costs) {
        // Memoization map to store results of subproblems
        Map<String, Integer> memo = new HashMap<>();
        
        // Helper function for recursion with memoization
        return helper(costs, 0, -1, memo);
    }

    private static int helper(int[][] costs, int house, int lastColor, Map<String, Integer> memo) {
        // Base case: If all houses are painted, return 0
        if (house == costs.length) {
            return 0;
        }

        // Create a unique key for the current state
        String key = house + "-" + lastColor;
        
        // Check if the result is already computed
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        // Initialize minimum cost to a large value
        int minCost = Integer.MAX_VALUE;

        // Try painting the current house with each color
        for (int color = 0; color < 3; color++) {
            if (color != lastColor) { // Ensure no two adjacent houses have the same color
                // Cost of painting the current house with 'color'
                int currentCost = costs[house][color];
                // Recursively calculate the cost for the remaining houses
                int totalCost = currentCost + helper(costs, house + 1, color, memo);
                // Update the minimum cost
                minCost = Math.min(minCost, totalCost);
            }
        }

        // Store the result in the memoization map
        memo.put(key, minCost);
        return minCost;
    }

    public static void main(String[] args) {
        // Example input
        int[][] costs = {
            {17, 2, 17},
            {16, 16, 5},
            {14, 3, 19}
        };

        // Calculate and print the minimum cost
        System.out.println(minCost(costs)); // Output: 10
    }
}