Suma mínima de caminos con obstáculos
Transporte el mejor coste entre las celdas
Suma mínima de caminos con obstáculos es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
De contar a calcular costos
Ahora cada celda contiene un valor y usted busca la ruta más barata hasta la esquina. El objetivo cambia de contar caminos a minimizar un costo.
Defina el estado
Sea dp[i][j] el costo total mínimo para llegar a la celda (i, j). La misma cuadrícula y los mismos movimientos, pero ahora se calculan sumas en lugar de conteos.
La transición
Elija el vecino de entrada más barato y después sume la celda actual. Esa elección de mínimo es el núcleo de la recurrencia.
dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])Marque los obstáculos
Un obstáculo es una celda sobre la que no puede situarse. Asígnele un costo infinito para que ningún camino que pase por ella sea nunca el mínimo.
INF = float('inf')Bloquéela correctamente
Cuando la cuadrícula marque una celda como bloqueada, establezca su dp en infinito y continúe. El paso de mínimo la evitará de forma natural.
if blocked(i, j):
dp[i][j] = INF
continueProteja el inicio
Si la celda inicial está bloqueada, no existe ningún camino. Compruébelo primero para no devolver un costo incorrecto.
Inicialice la primera celda
La celda inicial no tiene vecinos de los que proceder, así que su costo es simplemente su propio valor. Establezca dp[0][0] antes de ejecutar los bucles.
dp[0][0] = grid[0][0]Gestione los bordes
La fila superior solo recibe flujo desde la izquierda y la columna izquierda solo desde arriba. Gestione estos bordes para no leer fuera de la cuadrícula.
El infinito se propaga
Sumar infinito da como resultado infinito, por lo que una celda completamente aislada conserva su costo INF. Las celdas inalcanzables se identifican automáticamente.
Lea el resultado
El costo mínimo se encuentra en la celda inferior derecha. Si ese valor sigue siendo infinito, no existe ningún camino válido.
ans = dp[m-1][n-1]
if ans == INF:
ans = -1Cuándo falla el enfoque voraz
Avanzar siempre hacia el vecino más pequeño puede dejarle atrapado. Solo la DP completa garantiza el camino globalmente más barato, no una mirada voraz.
Comprobación rápida
¿Cómo consigue que la DP de caminos evite una celda bloqueada sin tratar de forma especial a cada vecino?
Repaso: camino mínimo con obstáculos
Elija el vecino más barato, sume el valor de la celda, establezca las celdas bloqueadas en infinito y lea la esquina. INF allí significa que no existe ningún camino. 🧱
Preguntas frecuentes
¿La lección «Suma mínima de caminos con obstáculos» es gratis?
Sí — el texto completo de «Suma mínima de caminos con obstáculos» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Suma mínima de caminos con obstáculos»?
Transporte el mejor coste entre las celdas Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Suma mínima de caminos con obstáculos»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Conteo de caminos en una cuadrícula
- Suma mínima de caminos con obstáculos
- Subsecuencia común más larga
- Distancia de edición paso a paso