Pintar casas pelo menor preço
A missão
Problema
Cada casa de uma fileira precisa ser pintada com uma de três cores, e pintar uma determinada casa com uma determinada cor tem seu próprio preço. Casas vizinhas não podem ter a mesma cor. Retorne o menor preço total para pintar a fileira inteira.
Exemplos
Input: costs = [[17, 2, 17],
[16, 16, 5],
[14, 3, 19]]
Output: 10
Por quê: pinte as casas com a segunda, a terceira e a segunda cor, por 2 + 5 + 3
Input: costs = [[7, 6, 2]]
Output: 2
Por quê: uma única casa simplesmente fica com a cor mais barata
Input: costs = []
Output: 0
Por quê: edge case: uma fileira vazia não custa nada
Dicas
0 / 3
Escolher a cor mais barata para cada casa de forma independente pode falhar, porque uma escolha barata pode forçar uma cara na casa ao lado. A decisão precisa levar em conta o que vem depois dela.
Percorra a fileira uma vez carregando três respostas correntes, uma por cor: o jeito mais barato de pintar tudo até aqui, dado que esta casa terminou com aquela cor.
Cada nova casa pega o próprio preço para uma cor e soma a mais barata das duas respostas correntes das outras duas cores. Calcule os três novos valores a partir dos três antigos de uma vez, siga em frente e pegue o menor dos três finais.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- each house has exactly three colour prices
Solução
A única coisa que importa para o resto da fileira é a cor da casa que acabou de ser pintada, então três totais correntes, um por cor, capturam todo o histórico. Cada casa reconstrói esses três a partir dos três anteriores, somando o próprio preço à mais barata das duas opções que não conflitam. Calcular os três ao mesmo tempo é importante, porque usar um valor recém-atualizado deixaria uma casa pegar emprestado de si mesma. O tempo é O(n) e o espaço é O(1), já que só três números são guardados.
def cheapest_painting(costs):
first = second = third = 0 # cheapest total ending in each of the colours
for a, b, c in costs:
# each colour pays its own price plus the better of the other two histories
first, second, third = (a + min(second, third),
b + min(first, third),
c + min(first, second))
return min(first, second, third)
print(cheapest_painting([[17, 2, 17], [16, 16, 5], [14, 3, 19]])) # -> 10
print(cheapest_painting([[7, 6, 2]])) # -> 2
print(cheapest_painting([])) # -> 0Travou na ideia, e não no código? O que é programação dinâmica? explica isso.