Paint House IV
Source: leetcode
Difficulty: Medium
Tags: array, dynamic-programming

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`




C++ solution:
class Solution {
public:
    long long minCost(int n, vector<vector<int>>& cost) {
        int m = n / 2;
        long long prev_dp[3][3];
        for (int c1 = 0; c1 < 3; ++c1)
            for (int c2 = 0; c2 < 3; ++c2)
                prev_dp[c1][c2] = LLONG_MAX;
        
        int i0 = 0, j0 = n - 1;
        for (int c1 = 0; c1 < 3; ++c1)
            for (int c2 = 0; c2 < 3; ++c2)
                if (c1 != c2)
                    prev_dp[c1][c2] = cost[i0][c1] + cost[j0][c2];
        
        for (int k = 1; k < m; ++k) {
            int i = k, j = n - 1 - k;
            long long curr_dp[3][3];
            for (int c1 = 0; c1 < 3; ++c1)
                for (int c2 = 0; c2 < 3; ++c2)
                    curr_dp[c1][c2] = LLONG_MAX;
            
            for (int prev_c1 = 0; prev_c1 < 3; ++prev_c1) {
                for (int prev_c2 = 0; prev_c2 < 3; ++prev_c2) {
                    if (prev_dp[prev_c1][prev_c2] == LLONG_MAX) continue;
                    
                    for (int curr_c1 = 0; curr_c1 < 3; ++curr_c1) {
                        if (curr_c1 == prev_c1) continue;
                        for (int curr_c2 = 0; curr_c2 < 3; ++curr_c2) {
                            if (curr_c2 == prev_c2 || curr_c1 == curr_c2) continue;
                            long long new_cost = prev_dp[prev_c1][prev_c2] + cost[i][curr_c1] + cost[j][curr_c2];
                            if (new_cost < curr_dp[curr_c1][curr_c2])
                                curr_dp[curr_c1][curr_c2] = new_cost;
                        }
                    }
                }
            }
            
            for (int c1 = 0; c1 < 3; ++c1)
                for (int c2 = 0; c2 < 3; ++c2)
                    prev_dp[c1][c2] = curr_dp[c1][c2];
        }
        
        long long min_cost = LLONG_MAX;
        for (int c1 = 0; c1 < 3; ++c1)
            for (int c2 = 0; c2 < 3; ++c2)
                if (c1 != c2 && prev_dp[c1][c2] < min_cost)
                    min_cost = prev_dp[c1][c2];
        
        return min_cost;
    }
};

Go solution:
func minCost(n int, cost [][]int) int64 {
    m := n / 2
    prevDp := make([][]int64, 3)
    for i := range prevDp {
        prevDp[i] = make([]int64, 3)
        for j := range prevDp[i] {
            prevDp[i][j] = math.MaxInt64
        }
    }

    left, right := 0, n-1
    for cl := 0; cl < 3; cl++ {
        for cr := 0; cr < 3; cr++ {
            if cl != cr {
                prevDp[cl][cr] = int64(cost[left][cl] + cost[right][cr])
            }
        }
    }

    for k := 1; k < m; k++ {
        currDp := make([][]int64, 3)
        for i := range currDp {
            currDp[i] = make([]int64, 3)
            for j := range currDp[i] {
                currDp[i][j] = math.MaxInt64
            }
        }
        left, right := k, n-1-k

        for prevCl := 0; prevCl < 3; prevCl++ {
            for prevCr := 0; prevCr < 3; prevCr++ {
                if prevCl == prevCr || prevDp[prevCl][prevCr] == math.MaxInt64 {
                    continue
                }
                for currCl := 0; currCl < 3; currCl++ {
                    if currCl == prevCl {
                        continue
                    }
                    for currCr := 0; currCr < 3; currCr++ {
                        if currCr == prevCr || currCl == currCr {
                            continue
                        }
                        total := prevDp[prevCl][prevCr] + int64(cost[left][currCl]+cost[right][currCr])
                        if total < currDp[currCl][currCr] {
                            currDp[currCl][currCr] = total
                        }
                    }
                }
            }
        }
        prevDp = currDp
    }

    minCost := int64(math.MaxInt64)
    for cl := 0; cl < 3; cl++ {
        for cr := 0; cr < 3; cr++ {
            if cl != cr && prevDp[cl][cr] < minCost {
                minCost = prevDp[cl][cr]
            }
        }
    }
    return minCost
}

Java solution:
class Solution {
    public long minCost(int n, int[][] cost) {
        int m = n / 2;
        long[][] prevDp = new long[3][3];
        for (int a = 0; a < 3; a++) {
            for (int b = 0; b < 3; b++) {
                prevDp[a][b] = Long.MAX_VALUE;
            }
        }
        int firstLeft = 0;
        int firstRight = n - 1;
        for (int a = 0; a < 3; a++) {
            for (int b = 0; b < 3; b++) {
                if (a != b) {
                    prevDp[a][b] = (long) cost[firstLeft][a] + cost[firstRight][b];
                }
            }
        }
        for (int p = 1; p < m; p++) {
            int left = p;
            int right = n - 1 - p;
            long[][] currDp = new long[3][3];
            for (int a = 0; a < 3; a++) {
                for (int b = 0; b < 3; b++) {
                    currDp[a][b] = Long.MAX_VALUE;
                }
            }
            for (int aPrev = 0; aPrev < 3; aPrev++) {
                for (int bPrev = 0; bPrev < 3; bPrev++) {
                    if (prevDp[aPrev][bPrev] == Long.MAX_VALUE) continue;
                    for (int a = 0; a < 3; a++) {
                        if (a == aPrev) continue;
                        for (int b = 0; b < 3; b++) {
                            if (b == bPrev || b == a) continue;
                            long newCost = prevDp[aPrev][bPrev] + cost[left][a] + cost[right][b];
                            if (newCost < currDp[a][b]) {
                                currDp[a][b] = newCost;
                            }
                        }
                    }
                }
            }
            prevDp = currDp;
        }
        long min = Long.MAX_VALUE;
        for (int a = 0; a < 3; a++) {
            for (int b = 0; b < 3; b++) {
                if (prevDp[a][b] < min) {
                    min = prevDp[a][b];
                }
            }
        }
        return min;
    }
}

JavaScript solution:
var minCost = function(n, cost) {
    let prevDp = Array.from({length: 3}, () => Array(3).fill(Infinity));
    const firstI = 0, firstJ = n - 1;
    for (let a = 0; a < 3; a++) {
        for (let b = 0; b < 3; b++) {
            if (a !== b) {
                prevDp[a][b] = cost[firstI][a] + cost[firstJ][b];
            }
        }
    }
    for (let step = 1; step < n / 2; step++) {
        const i = step, j = n - 1 - step;
        const currDp = Array.from({length: 3}, () => Array(3).fill(Infinity));
        for (let aPrev = 0; aPrev < 3; aPrev++) {
            for (let bPrev = 0; bPrev < 3; bPrev++) {
                if (prevDp[aPrev][bPrev] === Infinity) continue;
                for (let aCurr = 0; aCurr < 3; aCurr++) {
                    if (aCurr === aPrev) continue;
                    for (let bCurr = 0; bCurr < 3; bCurr++) {
                        if (bCurr === bPrev || bCurr === aCurr) continue;
                        const newCost = prevDp[aPrev][bPrev] + cost[i][aCurr] + cost[j][bCurr];
                        if (newCost < currDp[aCurr][bCurr]) {
                            currDp[aCurr][bCurr] = newCost;
                        }
                    }
                }
            }
        }
        prevDp = currDp;
    }
    let min = Infinity;
    for (let a = 0; a < 3; a++) {
        for (let b = 0; b < 3; b++) {
            if (a !== b && prevDp[a][b] < min) {
                min = prevDp[a][b];
            }
        }
    }
    return min;
};

Python solution:
class Solution:
    def minCost(self, n: int, cost: List[List[int]]) -> int:
        m = n // 2
        dp = {}
        first_left, first_right = 0, n - 1
        for c1 in range(3):
            for c2 in range(3):
                if c1 != c2:
                    total = cost[first_left][c1] + cost[first_right][c2]
                    dp[(c1, c2)] = total
        
        for i in range(1, m):
            left, right = i, n - 1 - i
            new_dp = {}
            for (prev_c1, prev_c2), prev_cost in dp.items():
                for curr_c1 in range(3):
                    if curr_c1 == prev_c1:
                        continue
                    for curr_c2 in range(3):
                        if curr_c2 == prev_c2 or curr_c1 == curr_c2:
                            continue
                        current_cost = prev_cost + cost[left][curr_c1] + cost[right][curr_c2]
                        key = (curr_c1, curr_c2)
                        if key not in new_dp or current_cost < new_dp.get(key, float('inf')):
                            new_dp[key] = current_cost
            dp = new_dp
        
        return min(dp.values())

Ruby solution:
def min_cost(n, cost)
  m = n / 2
  return 0 if m == 0

  inf = 1 << 60
  prev_dp = Array.new(3) { Array.new(3, inf) }

  i0 = 0
  j0 = n - 1
  (0..2).each do |c1|
    (0..2).each do |c2|
      if c1 != c2
        prev_dp[c1][c2] = cost[i0][c1] + cost[j0][c2]
      end
    end
  end

  (1...m).each do |k|
    i = k
    j = n - 1 - k
    curr_dp = Array.new(3) { Array.new(3, inf) }

    (0..2).each do |prev_c1|
      (0..2).each do |prev_c2|
        next if prev_dp[prev_c1][prev_c2] == inf

        (0..2).each do |curr_c1|
          next if curr_c1 == prev_c1

          (0..2).each do |curr_c2|
            next if curr_c2 == prev_c2 || curr_c1 == curr_c2

            total = prev_dp[prev_c1][prev_c2] + cost[i][curr_c1] + cost[j][curr_c2]
            curr_dp[curr_c1][curr_c2] = [curr_dp[curr_c1][curr_c2], total].min
          end
        end
      end
    end

    prev_dp = curr_dp
  end

  min_cost = inf
  (0..2).each do |c1|
    (0..2).each do |c2|
      if c1 != c2 && prev_dp[c1][c2] < min_cost
        min_cost = prev_dp[c1][c2]
      end
    end
  end

  min_cost
end