Colheita sem vizinhos
A missão
Problema
Um robô de colheita percorre uma única fileira de lotes, e cada lote tem uma produção conhecida. O braço dele precisa descansar depois de cada colheita, então ele nunca pode colher dois lotes que ficam lado a lado. Retorne a maior produção total que o robô consegue juntar em uma única passada. As produções são números inteiros a partir de 0, e a fileira pode estar vazia.
Exemplos
Input: yields = [2, 7, 9, 3, 1]
Output: 12
Por quê: colha os lotes 0, 2 e 4 para obter 2 + 9 + 1
Input: yields = [5, 1, 1, 5]
Output: 10
Por quê: os dois lotes das pontas não são vizinhos, então os dois podem ser colhidos
Input: yields = []
Output: 0
Por quê: edge case: uma fileira vazia não produz nada
Dicas
0 / 3
Escolher o maior lote primeiro pode bloquear dois bons vizinhos. Pense na fileira um lote por vez, em vez de tudo de uma vez.
Ao chegar a um lote, você enfrenta exatamente uma decisão: colher ou pular. Cada escolha depende só do que aconteceu no lote imediatamente anterior.
Carregue dois totais correntes: o melhor resultado se o lote anterior foi colhido e o melhor se ele foi pulado. Colher o lote atual estende o total de quem pulou; pular mantém o melhor dos dois.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Restrições
- yields are integers ≥ 0
- the row may be empty
Solução
Em cada lote, o melhor total até ali vem de um de dois estados: o lote anterior foi colhido ou não foi. Colher o lote atual só é permitido a partir do estado pulado, e pular mantém o estado que estava melhor, então duas variáveis substituem uma tabela inteira. A resposta é o melhor estado depois do último lote. O tempo é O(n), com uma única passada, e o espaço é O(1).
def best_harvest(yields):
took, skipped = 0, 0 # best total if the last plot was harvested / left alone
for y in yields:
# harvesting now needs the previous plot skipped; skipping keeps the better state
took, skipped = skipped + y, max(took, skipped)
return max(took, skipped)
print(best_harvest([2, 7, 9, 3, 1])) # -> 12
print(best_harvest([5, 1, 1, 5])) # -> 10
print(best_harvest([])) # -> 0Travou na ideia, e não no código? House Robber explica isso.