# 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& houses, vector>& 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>(m, vector(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>> dp; int minCost(const vector& houses, const vector>& 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; } }