LeetCode 256: Paint House

Explanation:

The problem asks us to paint n houses with k different colors. Each house should be painted with a certain color, and no two adjacent houses can have the same color. We are given a list of costs, where costs[i][j] represents the cost of painting house i with color j.

To minimize the total cost, we need to find the minimum cost to paint all houses without having the same color for adjacent houses.

We can solve this problem using dynamic programming. We will maintain a 2D array, dp, where dp[i][j] represents the minimum cost of painting the first i houses with the i-th house painted with color j. At each step, we will consider the minimum cost of painting the current house with each color, based on the previous house's color choices.

Finally, the minimum cost will be the minimum value in the last row of the dp array.

: :

class Solution {
    public int minCost(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        
        int n = costs.length;
        int k = costs[0].length;
        int[][] dp = new int[n + 1][k];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < k; j++) {
                dp[i][j] = costs[i - 1][j] + Math.min(dp[i - 1][(j + 1) % k], dp[i - 1][(j + 2) % k]);
            }
        }
        
        int minCost = Integer.MAX_VALUE;
        for (int j = 0; j < k; j++) {
            minCost = Math.min(minCost, dp[n][j]);
        }
        
        return minCost;
    }
}