Caminho mais barato em um grid
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
Escolher o vizinho mais barato a cada passo é uma armadilha, já que um passo barato pode levar a uma região cara. O número de caminhos cresce rápido demais para testar todos.
As únicas formas de entrar em uma célula são pela célula de cima e pela célula da esquerda. Então o menor custo para chegar a uma célula é o custo dela mais o menor desses dois custos mínimos.
Monte uma tabela do tamanho do grid. A entrada do canto superior esquerdo é o próprio custo, a primeira linha só pode vir da esquerda e a primeira coluna só de cima. Toda outra entrada é o custo dela mais o mínimo entre a entrada de cima e a da esquerda. A resposta é a entrada do canto inferior direito.
- Tempo-alvo
- O(rows · cols)
- Espaço-alvo
- O(rows · cols)
Restrições
- every cell cost is non-negative
Solução
Todo caminho que entra em uma célula chega por cima ou pela esquerda, então o jeito mais barato de alcançá-la estende o mais barato desses dois caminhos mínimos. Preencher a tabela linha por linha garante que as duas vizinhas já sejam definitivas antes de uma célula precisar delas. A primeira linha e a primeira coluna têm uma única entrada possível, e por isso são tratadas à parte. O tempo é O(rows · cols) e o espaço é O(rows · cols); como cada linha só lê a linha de cima, uma única linha da tabela basta se a memória importar.
def cheapest_path(grid):
rows, cols = len(grid), len(grid[0])
cost = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
cost[r][c] = grid[r][c]
elif r == 0:
cost[r][c] = cost[r][c - 1] + grid[r][c] # top row: only from the left
elif c == 0:
cost[r][c] = cost[r - 1][c] + grid[r][c] # left column: only from above
else:
cost[r][c] = min(cost[r - 1][c], cost[r][c - 1]) + grid[r][c]
return cost[-1][-1]
print(cheapest_path([[1, 3, 1], [1, 5, 1], [4, 2, 1]])) # -> 7
print(cheapest_path([[2, 1, 4], [3, 1, 1]])) # -> 5
print(cheapest_path([[7]])) # -> 7Travou na ideia, e não no código? DP em grids explica isso.