This problem looks busy at first, but the accepted solution is built around one steady invariant. For 1473. Paint House III, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: DFS + memoization, dynamic programming, backtracking.
The notes already sitting in the source point us in the right direction:
- TLE
- 24 / 59 test cases passed.
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are backtrack, minCost, dfs.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//TLE
02//24 / 59 test cases passed.
03class Solution {
04public:
05 int ans;
06
07 void backtrack(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target, int start, int curCost){
08 // cout << "start: " << start << ", curCost: " << curCost << ", target: " << target << endl;
09 // cout << "houses: ";
10 // for(int i = 0; i < houses.size(); i++){
11 // cout << houses[i] << " ";
12 // }
13 // cout << endl;
14
15 if(start == m){
16 //reach end of houses
17 //no more neighborhoods to add
18 if(target == 0){
19 ans = min(ans, curCost);
20 // cout << "ans: " << ans << endl;
21 }
22 }else if(houses[start] != 0){
23 //current house is already painted
24 int newtarget = target;
25 if(start == 0){
26 // cout << "start is 0" << endl;
27 newtarget = target-1;
28 }else if(start > 0 && houses[start-1] != 0 && houses[start] != houses[start-1]){
29 // cout << "color not equal to last" << endl;
30 newtarget = target-1;
31 }
32 if(newtarget < 0) return;
33 backtrack(houses, cost, m, n, newtarget, start+1, curCost);
34 }else{
35 for(int i = 0; i < n; i++){
36 int newtarget = target;
37 if(start == 0){
38 // cout << "start is 0" << endl;
39 newtarget = target-1;
40 }else if(start > 0 && houses[start-1] != 0 && i+1 != houses[start-1]){
41 // cout << "color not equal to last" << endl;
42 newtarget = target-1;
43 }
44 if(newtarget < 0) continue;
45 houses[start] = i+1;
46 // cout << "target: " << target << " -> " << newtarget << endl;
47 backtrack(houses, cost, m, n, newtarget, start+1, curCost+cost[start][i]);
48 houses[start] = 0;
49 }
50 }
51 };
52
53 int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
54 ans = INT_MAX;
55 backtrack(houses, cost, m, n, target, 0, 0);
56 return (ans == INT_MAX) ? -1 : ans;
57 }
58};
59
60//dfs + memorization
61//TLE
62//25 / 60 test cases passed.
63//https://leetcode.com/problems/paint-house-iii/discuss/674313/Simple-Python-explanation-and-why-I-prefer-top-down-DP-to-bottom-up
64//time: O(m*n^2*target), space: O(m*n*target)
65class Solution {
66public:
67 /*
68 m == houses.length == cost.length
69 n == cost[i].length
70 1 <= m <= 100
71 1 <= n <= 20
72 1 <= target <= m
73 0 <= houses[i] <= n
74 1 <= cost[i][j] <= 10^4
75 max cost is 10^4 * 100 = 1e6
76 */
77 int MAX = 1e6+1;
78 vector<int> houses;
79 vector<vector<int>> cost;
80 int m, n, target;
81 vector<vector<vector<int>>> memo;
82
83 int dfs(int start, int t, int prevColor){
84 // cout << "(" << start << ", " << t << ", " << prevColor << ")" << endl;
85 if(t < 0 || t > m-start){
86 /*
87 t > m-start:
88 we only have (m-1)-(start-1) = m-start houses remained,
89 but we need more neighborhoods
90 */
91 // cout << "(" << start << ", " << t << ", " << prevColor << "): " << MAX << endl;
92 return MAX;
93 }else if(start == m){
94 // cout << "(" << start << ", " << t << ", " << prevColor << "): " << ((t == 0) ? 0 : MAX) << endl;
95 return (t == 0) ? 0 : MAX;
96 }else if(memo[start][t][prevColor+1] < MAX){
97 return memo[start][t][prevColor+1];
98 }else if(houses[start] != 0){
99 memo[start][t][prevColor+1] = dfs(start+1, t - (houses[start] != prevColor), houses[start]);
100 // cout << "(" << start << ", " << t << ", " << prevColor << "): " << memo[start][t][prevColor+1] << endl;
101 return memo[start][t][prevColor+1];
102 }else{
103 /*
104 note that color = 0 means unpainted,
105 and color's range is [1,n]!
106 */
107 for(int color = 1; color <= n; color++){
108 int tmp = dfs(start+1, t - (color != prevColor), color);
109 if(tmp < MAX){
110 memo[start][t][prevColor+1] = min(memo[start][t][prevColor+1], cost[start][color-1] + tmp);
111 }
112 // memo[start][t][prevColor] = min(memo[start][t][prevColor], cost[start][color-1] + dfs(start+1, t - (color != prevColor), color));
113 }
114 // cout << "(" << start << ", " << t << ", " << prevColor << "): " << memo[start][t][prevColor+1] << endl;
115 return memo[start][t][prevColor+1];
116 }
117 };
118
119 int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
120 this->houses = houses;
121 this->cost = cost;
122 this->m = m;
123 this->n = n;
124 this->target = target;
125
126 //t: [0, target]
127 //prevColor: [-1, n] -> [0, n+1]
128 memo = vector<vector<vector<int>>>(m, vector<vector<int>>(target+1, vector<int>(n+2, MAX)));
129
130 /*
131 set 0th color as -1,
132 because when we paint 0th house,
133 we will consume one neighborhood anyway
134 */
135 int ans = dfs(0, target, -1);
136 return (ans >= MAX) ? -1 : ans;
137 }
138};
139
140//dfs + memorization(previous method + speed up)
141//Runtime: 60 ms, faster than 84.48% of C++ online submissions for Paint House III.
142//Memory Usage: 20.1 MB, less than 100.00% of C++ online submissions for Paint House III.
143/*
144speed up 1: initialize memo as 0 rather than MAX and do corresponding changes
145speed up 2: in the last "else" part, use an additional variable "ans" rather than
146memo[start][t][prevColor+1] = min(memo[start][t][prevColor+1], ...)
147speed up 3: don't copy houses and cost, pass them to function by reference
148*/
149class Solution {
150public:
151 int MAX = 1e6+1;
152 int m, n, target;
153 vector<vector<vector<int>>> memo;
154
155 int dfs(vector<int>& houses, vector<vector<int>>& cost, int start, int t, int prevColor){
156 if(t < 0 || t > m-start){
157 return MAX;
158 }else if(start == m){
159 return (t == 0) ? 0 : MAX;
160 }else if(memo[start][t][prevColor+1] != 0){
161 return memo[start][t][prevColor+1];
162 }else if(houses[start] != 0){
163 memo[start][t][prevColor+1] = dfs(houses, cost, start+1, t - (houses[start] != prevColor), houses[start]);
164 return memo[start][t][prevColor+1];
165 }else{
166 int ans = MAX;
167 for(int color = 1; color <= n; color++){
168 ans = min(ans, cost[start][color-1] + dfs(houses, cost, start+1, t - (color != prevColor), color));
169 }
170 return memo[start][t][prevColor+1] = ans;
171 }
172 };
173
174 int minCost(vector<int>& houses, vector<vector<int>>& cost, int m, int n, int target) {
175 this->m = m;
176 this->n = n;
177 this->target = target;
178
179 memo = vector<vector<vector<int>>>(m, vector<vector<int>>(target+1, vector<int>(n+2, 0)));
180
181 int ans = dfs(houses, cost, 0, target, -1);
182 return (ans >= MAX) ? -1 : ans;
183 }
184};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.