Skip to content

3429. Paint House IV 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
 public:
  long long minCost(int n, vector<vector<int>>& costs) {
    constexpr int kInvalidColor = 3;
    vector<vector<vector<long>>> mem(
        n / 2, vector<vector<long>>(4, vector<long>(4, -1)));
    return minCost(costs, 0, kInvalidColor, kInvalidColor, mem);
  }

 private:
  long minCost(const vector<vector<int>>& costs, int i, int prevLeftColor,
               int prevRightColor, vector<vector<vector<long>>>& mem) {
    if (i == costs.size() / 2)
      return 0;
    if (mem[i][prevLeftColor][prevRightColor] != -1)
      return mem[i][prevLeftColor][prevRightColor];

    long res = LONG_MAX;

    for (const int leftColor : getValidColors(prevLeftColor))
      for (const int rightColor : getValidColors(prevRightColor)) {
        if (leftColor == rightColor)
          continue;
        const long leftCost = costs[i][leftColor];
        const long rightCost = costs[costs.size() - 1 - i][rightColor];
        res = min(res, leftCost + rightCost +
                           minCost(costs, i + 1, leftColor, rightColor, mem));
      }

    return mem[i][prevLeftColor][prevRightColor] = res;
  }

  vector<int> getValidColors(int prevColor) {
    vector<int> validColors;
    for (int color = 0; color < 3; ++color)
      if (color != prevColor)
        validColors.push_back(color);
    return validColors;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
  public long minCost(int n, int[][] costs) {
    final int INVALID_COLOR = 3;
    Long[][][] mem = new Long[n / 2][4][4];
    return minCost(costs, 0, INVALID_COLOR, INVALID_COLOR, mem);
  }

  private long minCost(int[][] costs, int i, int prevLeftColor, int prevRightColor,
                       Long[][][] mem) {
    if (i == costs.length / 2)
      return 0;
    if (mem[i][prevLeftColor][prevRightColor] != null)
      return mem[i][prevLeftColor][prevRightColor];

    long res = Long.MAX_VALUE;

    for (final int leftColor : getValidColors(prevLeftColor))
      for (final int rightColor : getValidColors(prevRightColor)) {
        if (leftColor == rightColor)
          continue;
        final long leftCost = costs[i][leftColor];
        final long rightCost = costs[costs.length - 1 - i][rightColor];
        res =
            Math.min(res, leftCost + rightCost + minCost(costs, i + 1, leftColor, rightColor, mem));
      }

    return mem[i][prevLeftColor][prevRightColor] = res;
  }

  private List<Integer> getValidColors(int prevColor) {
    List<Integer> validColors = new ArrayList<>();
    for (int color = 0; color < 3; ++color)
      if (color != prevColor)
        validColors.add(color);
    return validColors;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def minCost(self, n: int, costs: list[list[int]]) -> int:
    INVALID_COLOR = 3

    def getValidColors(prevColor: int) -> list[int]:
      return [color for color in range(3) if color != prevColor]

    @functools.lru_cache(None)
    def minCost(i: int, prevLeftColor: int, prevRightColor: int) -> int:
      if i == len(costs) // 2:
        return 0
      res = math.inf
      for leftColor in getValidColors(prevLeftColor):
        for rightColor in getValidColors(prevRightColor):
          if leftColor == rightColor:
            continue
          leftCost = costs[i][leftColor]
          rightCost = costs[-1 - i][rightColor]
          res = min(res, leftCost + rightCost +
                    minCost(i + 1, leftColor, rightColor))
      return res

    return minCost(0, INVALID_COLOR, INVALID_COLOR)