Skip to content

3737. Paint House Iv

3737. Paint House IV

Medium

You are given an even integer n representing the number of houses arranged in a straight line, and a 2D array cost of size n x 3, where cost[i][j] represents the cost of painting house i with color j + 1.

The houses will look beautiful if they satisfy the following conditions:

  • No two adjacent houses are painted the same color.
  • Houses equidistant from the ends of the row are not painted the same color. For example, if n = 6, houses at positions (0, 5), (1, 4), and (2, 3) are considered equidistant.

Return the minimum cost to paint the houses such that they look beautiful.

 

Example 1:

Input: n = 4, cost = [[3,5,7],[6,2,9],[4,8,1],[7,3,5]]

Output: 9

Explanation:

The optimal painting sequence is [1, 2, 3, 2] with corresponding costs [3, 2, 1, 3]. This satisfies the following conditions:

  • No adjacent houses have the same color.
  • Houses at positions 0 and 3 (equidistant from the ends) are not painted the same color (1 != 2).
  • Houses at positions 1 and 2 (equidistant from the ends) are not painted the same color (2 != 3).

The minimum cost to paint the houses so that they look beautiful is 3 + 2 + 1 + 3 = 9.

Example 2:

Input: n = 6, cost = [[2,4,6],[5,3,8],[7,1,9],[4,6,2],[3,5,7],[8,2,4]]

Output: 18

Explanation:

The optimal painting sequence is [1, 3, 2, 3, 1, 2] with corresponding costs [2, 8, 1, 2, 3, 2]. This satisfies the following conditions:

  • No adjacent houses have the same color.
  • Houses at positions 0 and 5 (equidistant from the ends) are not painted the same color (1 != 2).
  • Houses at positions 1 and 4 (equidistant from the ends) are not painted the same color (3 != 1).
  • Houses at positions 2 and 3 (equidistant from the ends) are not painted the same color (2 != 3).

The minimum cost to paint the houses so that they look beautiful is 2 + 8 + 1 + 2 + 3 + 2 = 18.

 

Constraints:

  • 2 <= n <= 105
  • n is even.
  • cost.length == n
  • cost[i].length == 3
  • 0 <= cost[i][j] <= 105

Solution

class Solution {
    private long dp[][][][];
    public long minCost(int n, int[][] cost) {
        dp = new long[n + 1][4][4][3];
        for (long current[][][] : dp) for (long current1[][] : current) for (long current2[] : current1) Arrays.fill(current2, -1);
        return solve(n, 0, cost, 3, 3, 0);   
    }
    private long solve(int n, int idx, int cost[][], int prev1, int prev2, int start) {
        if (idx >= n / 2) return 0;
        long ans = Long.MAX_VALUE;
        if (dp[idx][prev1][prev2][start] != - 1) return dp[idx][prev1][prev2][start];
        if (start == 0) {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i != j) {
                        long ans1 = (long) cost[idx][i] + (long) cost[n - 1 - idx][j] + solve(n, idx + 1, cost, i, j, 1);
                        ans = Math.min(ans, ans1);
                    }
                }
            }
        } 
        else {
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (prev1 != i && prev2 != j && i != j) {
                        long ans1 = (long) cost[idx][i] + (long) cost[n-1-idx][j] + solve(n, idx + 1, cost, i, j, start);
                        ans = Math.min(ans, ans1);
                    }
                }
            }
        }
        return dp[idx][prev1][prev2][start] = ans;
    }
}

Complexity Analysis

  • Time Complexity: O(?)
  • Space Complexity: O(?)

Explanation

[Add detailed explanation here]