Rutas únicas y suma mínima de rutas en cuadrículas

Unique Paths (LeetCode 62) plantea la siguiente pregunta: en una cuadrícula de m×n, ¿cuántos caminos distintos van de la esquina superior izquierda a la esquina inferior derecha si solo puede moverse a la derecha o hacia abajo? Para una cuadrícula de 3×7, la respuesta es 28. La idea clave es que todo camino hasta la celda (i,j) debe proceder de (i-1,j) (arriba) o de (i,j-1) (izquierda), lo que da lugar a una formulación natural de DP bidimensional.

Defina dp[i][j] como el número de caminos hasta la celda (i,j). La primera fila y la primera columna contienen únicamente 1 (solo hay una forma de llegar a cualquier celda de la fila superior o de la columna situada más a la izquierda). Para las demás celdas: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Rellene la tabla fila por fila; la respuesta es dp[m-1][n-1]. Complejidad temporal: O(m×n); espacio: O(m×n), reducible a O(n).

Dado que dp[i][j] solo depende de la fila actual y de la fila anterior, puede sustituir la tabla bidimensional completa por un único array unidimensional. Inicialice todos los valores a 1 y, para cada fila, actualice el array sobre el mismo sitio: dp[j] += dp[j-1]. Después de procesar la fila i, dp[j] contiene el valor que tenía dp[i][j] en la tabla bidimensional. Este es un patrón de optimización habitual en problemas de DP bidimensional.

Unique Paths II (LeetCode 63) añade obstáculos (celdas marcadas con 1) a la cuadrícula. Cualquier camino que atraviese un obstáculo no es válido, por lo que dp[i][j] = 0 si obstacle[i][j] == 1. En caso contrario, la recurrencia es la misma: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Si el inicio o el final están bloqueados, el resultado es inmediatamente 0. Inicialice los casos base con cuidado: una vez que aparece un 1 en la primera fila o columna, todas las celdas posteriores de esa fila o columna son 0.

Minimum Path Sum (LeetCode 64) plantea la siguiente pregunta: dada una cuadrícula de m×n llena de enteros no negativos, encuentre el camino desde la esquina superior izquierda hasta la inferior derecha que minimice la suma de todos los números del camino (moviéndose únicamente a la derecha o hacia abajo). Por ejemplo, en [[1,3,1],[1,5,1],[4,2,1]], el camino 1→3→1→1→1 tiene suma 7. El estado de DP es el mismo que en Unique Paths, pero ahora la recurrencia utiliza el mínimo en lugar de la suma.

Defina dp[i][j] como el coste mínimo para llegar a la celda (i,j). Caso base: dp[0][0] = grid[0][0]. Primera fila: dp[0][j] = dp[0][j-1] + grid[0][j] (la única forma es llegar desde la izquierda). Primera columna: dp[i][0] = dp[i-1][0] + grid[i][0] (la única forma es llegar desde arriba). Caso general: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Se trata de una traducción directa del principio de optimalidad.

Si se permite modificar la cuadrícula de entrada, puede actualizarla in situ para evitar asignar una tabla de DP independiente. Esto reduce el espacio auxiliar a O(1) (sin contar la entrada). En ocasiones, los entrevistadores preguntan por esta optimización; aclare si se permite modificar la entrada antes de hacerlo. Si no se permite, el truco del array unidimensional rotativo ofrece un espacio O(n) sin modificar la entrada.

Triangle (LeetCode 120) pide encontrar la suma mínima de un camino desde la parte superior hasta la inferior de un array triangular, donde cada paso lleva a un número adyacente de la fila inferior. La DP de abajo arriba es la opción más clara: comience en la penúltima fila y, para cada celda, sume el mínimo de las dos celdas situadas directamente debajo. Esto evita tener que hacer un seguimiento de los índices iniciales y hace que el resultado ascienda de forma natural hasta el vértice superior.

Dungeon Game (LeetCode 174) pide encontrar la salud inicial mínima necesaria para rescatar a una princesa en la esquina inferior derecha de una cuadrícula con celdas negativas (daño) y positivas (curación). Debe moverse a la derecha o hacia abajo. El truco consiste en rellenar la tabla de DP hacia atrás (desde la esquina inferior derecha hasta la superior izquierda), calculando la salud mínima necesaria en cada celda. En cada celda: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). La salud debe mantenerse siempre al menos en 1.

Los problemas de DP en cuadrículas comparten la misma estructura, pero difieren en la dirección en la que se rellenan y en la operación de transición: Unique Paths utiliza la suma (cuenta todas las formas). Min Path Sum utiliza el mínimo (optimiza). Dungeon Game se rellena hacia atrás (calcula la salud necesaria a partir del futuro). Al enfrentarse a una nueva DP de cuadrícula, pregúntese: (1) ¿Qué representa cada celda? (2) ¿En qué dirección debo rellenar? (3) ¿Qué operación combina las celdas vecinas? Las respuestas a estas tres preguntas revelan la solución completa.

Todos los problemas de DP en cuadrículas de esta lección se ejecutan en un tiempo O(m×n). El espacio va desde O(m×n) para una tabla completa hasta O(n) con un array unidimensional rotativo, y O(1) de espacio auxiliar cuando la cuadrícula se puede modificar in situ. En las entrevistas, mencione la optimización de espacio O(n) después de presentar la solución O(m×n); esto demuestra que conoce las ventajas y desventajas. Para todos los problemas, considere también si existe un atajo greedy, como la fórmula matemática de Unique Paths.

Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

En esta lección ha aprendido que Unique Paths rellena una tabla bidimensional con dp[i][j] = dp[i-1][j] + dp[i][j-1] y se puede calcular en O(1) mediante combinatoria, que Min Path Sum utiliza la misma estructura, pero sustituye la suma por min para calcular el coste óptimo del camino, y que todos los problemas de DP en cuadrículas comparten el patrón de definir un estado por celda y elegir un operador de transición (suma, mínimo, máximo). A continuación, exploraremos la subsecuencia común más larga mediante DP bidimensional sobre dos secuencias.