Pular para o conteúdo

Caminho mais barato em um grid

Fácil#grid-dp#2d-dp~20 min

A missão

Problema

Um grid guarda um custo não negativo em cada célula. Você começa na célula do canto superior esquerdo e precisa chegar à célula do canto inferior direito, movendo-se só para a direita ou para baixo. Retorne a menor soma possível dos custos das células por onde você passa, incluindo a primeira e a última.

Exemplos

Input:  grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Por quê: direita, direita, baixo, baixo passa por 1, 3, 1, 1, 1 e evita o 5 do meio
Input:  grid = [[2, 1, 4], [3, 1, 1]]
Output: 5
Por quê: direita, baixo, direita passa por 2, 1, 1, 1
Input:  grid = [[7]]
Output: 7
Por quê: edge case: o início também é o fim

Dicas

0 / 3

Tempo-alvo
O(rows · cols)
Espaço-alvo
O(rows · cols)

Restrições

  • every cell cost is non-negative

Travou na ideia, e não no código? DP em grids explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado