-
Notifications
You must be signed in to change notification settings - Fork 39
/
solution_19.py
28 lines (22 loc) · 1.36 KB
/
solution_19.py
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
def coding_problem_19(house_costs):
"""
A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost
while ensuring that no two neighboring houses are of the same color. Given an N by K matrix where the nth row and
kth column represents the cost to build the nth house with kth color, return the minimum cost.
Example:
>>> house_size = [1, 2, 4, 2] # size of the house
>>> color_cost = [1, 2, 4] # cost of paint for each color
>>> house_costs = [[cc * hs for cc in color_cost] for hs in house_size] # 4 houses, 3 colors
>>> coding_problem_19(house_costs) # [1,2,4,2] . [1,2,1,2] == 1*1 + 2*2 + 1*4 + 2*2 == 13
13
Notes: this is dynamic programming in disguise. We assign a color to each house in order, and keep
track of the minimum cost associated with each choice of color. These costs are the minimum over all
possible permutation in which the last added house is of a particular color.
"""
best_costs = [0] * len(house_costs[0])
for color_costs in house_costs: # color_costs are those paid to paint last added house with a certain color
best_costs = [color_costs[i] + min(best_costs[:i] + best_costs[i + 1:]) for i in range(len(best_costs))]
return min(best_costs)
if __name__ == '__main__':
import doctest
doctest.testmod(verbose=True)