Soma Mínima de Caminho com Obstáculos
Propague o menor custo pelas células.
Soma Mínima de Caminho com Obstáculos é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Da contagem ao custo
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.
Defina o estado
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.
A transição
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.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Marque os obstáculos
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.
INF = float('inf')Bloqueie de forma simples
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.
if blocked(i, j):
dp[i][j] = INF
continueProteja o início
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.
Inicialize a primeira célula
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.
dp[0][0] = grid[0][0]Trate as bordas
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.
O infinito se propaga
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.
Leia o resultado
O menor custo fica na célula inferior direita. Se esse valor ainda for infinito, não existe nenhum caminho válido.
ans = dp[m-1][n-1]
if ans == INF:
ans = -1Quando a estratégia gulosa falha
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.
Verificação rápida
Como fazer a DP de caminhos evitar uma célula bloqueada sem tratar cada vizinho de maneira especial?
Recapitulação: menor caminho com obstáculos
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. 🧱
Perguntas Frequentes
A aula “Soma Mínima de Caminho com Obstáculos” é grátis?
Sim — o texto completo de “Soma Mínima de Caminho com Obstáculos” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Soma Mínima de Caminho com Obstáculos”?
Propague o menor custo pelas células. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Soma Mínima de Caminho com Obstáculos”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Contagem de Caminhos em uma Grade
- Soma Mínima de Caminho com Obstáculos
- Maior Subsequência Comum
- Distância de Edição Passo a Passo