Pular para o conteúdo

Pintar casas pelo menor preço

Fácil#bottom-up-dp#rolling-variables~20 min

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

Tempo-alvo
O(n)
Espaço-alvo
O(1)

Restrições

  • each house has exactly three colour prices

Travou na ideia, e não no código? O que é programação dinâmica? explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado