Skip to content

1473. Paint House III 👍

  • Time: $O(\texttt{target} \cdot mn^2)$
  • Space: $O(tmn)$
 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
class Solution {
 public:
  int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n,
              int target) {
    // dp[k][i][prevColor] := min cost to paint houses[i..m) to k neighborhoods
    // W/ houses[i - 1]'s color = prevColor
    dp.resize(target + 1, vector<vector<int>>(m, vector<int>(n + 1)));

    // Init: prevColor = 0 (virtual neighbor)
    const int c = minCost(houses, cost, m, n, target, 0, 0);
    return c == kMax ? -1 : c;
  }

 private:
  static constexpr int kMax = 1'000'001;
  vector<vector<vector<int>>> dp;

  int minCost(const vector<int>& houses, const vector<vector<int>>& cost,
              const int& m, const int& n, int k, int i, int prevColor) {
    if (i == m || k < 0)
      return k == 0 ? 0 : kMax;
    if (dp[k][i][prevColor] > 0)
      return dp[k][i][prevColor];
    if (houses[i] > 0)  // Painted last year
      return minCost(houses, cost, m, n, k - (prevColor != houses[i]), i + 1,
                     houses[i]);

    int ans = kMax;

    // Try to paint houses[i] with each color in 1..n
    for (int color = 1; color <= n; ++color)
      ans = min(ans, cost[i][color - 1] + minCost(houses, cost, m, n,
                                                  k - (prevColor != color),
                                                  i + 1, color));

    return dp[k][i][prevColor] = ans;
  }
};

 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
class Solution {
  public int minCost(int[] houses, int[][] cost, int m, int n, int target) {
    // dp[k][i][prevColor] := min cost to paint houses[i..m) to k neighborhoods
    // W/ houses[i - 1]'s color = prevColor
    dp = new int[target + 1][m][n + 1];

    // Init: prevColor = 0 (virtual neighbor)
    final int c = minCost(houses, cost, m, n, target, 0, 0);
    return c == kMax ? -1 : c;
  }

  private static final int kMax = 1_000_001;
  private int[][][] dp;

  public int minCost(int[] houses, int[][] cost, int m, int n, int k, int i, int prevColor) {
    if (i == m || k < 0)
      return k == 0 ? 0 : kMax;
    if (dp[k][i][prevColor] > 0)
      return dp[k][i][prevColor];
    if (houses[i] > 0) // Painted last year
      return minCost(houses, cost, m, n, k - (prevColor == houses[i] ? 0 : 1), i + 1, houses[i]);

    int ans = kMax;

    // Try to paint houses[i] with each color in 1..n
    for (int color = 1; color <= n; ++color)
      ans = Math.min(ans,
                     cost[i][color - 1] + minCost(houses, cost, m, n,
                                                  k - (prevColor == color ? 0 : 1), i + 1, color));

    return dp[k][i][prevColor] = ans;
  }
}