Soma Mínima de Caminho com Obstáculos

Agora cada célula contém um valor e você quer a rota mais barata até o canto. O objetivo muda de contar caminhos para minimizar um custo.

Considere dp[i][j] como o menor custo total para chegar à célula (i, j). A mesma grade, os mesmos movimentos, mas agora acompanhamos somas em vez de contagens.

Escolha o mais barato dos dois vizinhos de entrada e depois some o valor da célula atual. Essa escolha do mínimo é o coração da recorrência.

Um obstáculo é uma célula onde você não pode ficar. Atribua a ela um custo infinito para que qualquer caminho que passe por ela nunca seja o mínimo.

Quando a grade marcar uma célula como bloqueada, basta atribuir infinito ao seu dp e continuar. A etapa do mínimo a evitará naturalmente.

Se a própria célula inicial estiver bloqueada, não haverá caminho algum. Verifique isso primeiro para não retornar um custo inválido.

Não há vizinhos de onde se possa chegar à célula inicial, portanto seu custo é apenas o próprio valor. Defina dp[0][0] antes de executar os laços.

A linha superior só recebe valores da esquerda, e a coluna esquerda só recebe valores de cima. Trate essas bordas para nunca acessar uma posição fora da grade.

Somar algo ao infinito continua resultando em infinito, portanto uma célula completamente isolada mantém seu custo INF. As células inalcançáveis se identificam automaticamente.

O menor custo fica na célula inferior direita. Se esse valor ainda for infinito, não existe nenhum caminho válido.

Escolher sempre o vizinho menor pode prender você. Somente a DP completa garante o caminho globalmente mais barato, e não uma escolha gulosa imediata.

Como fazer a DP de caminhos evitar uma célula bloqueada sem tratar cada vizinho de maneira especial?

Escolha o vizinho mais barato, some o valor da célula, atribua infinito às células bloqueadas e leia o canto. INF nesse ponto significa nenhum caminho. 🧱