DP en LeetCode: 3 problemas con fórmulas de recurrencia

Programación Dinámica: Un Enfoque Intuitivo para Tres Problemas de LeetCode

La programación dinámica (PD) resuelve problemas de conteo y optimización mediante relaciones de recurrencia. Examinemos los problemas 62 (Caminos Únicos), 64 (Suma Mínima de Caminos) y 70 (Subir Escaleras). Cada uno demuestra características clave de la PD: subestructura óptima y subproblemas superpuestos.

Caminos Únicos: Contando Rutas en una Cuadrícula

Un robot se mueve en una cuadrícula de m × n desde (0,0) hasta (m-1,n-1), moviéndose solo hacia la derecha o hacia abajo. Encuentra el número de caminos únicos.

Cualquier camino consiste en (m-1) pasos hacia abajo y (n-1) pasos hacia la derecha. Una solución combinatoria usa el coeficiente binomial C(m+n-2, m-1). Sin embargo, en entrevistas se espera un enfoque algorítmico.

Define dp[i][j] como el número de caminos a la celda (i,j). Relación de recurrencia:

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Condiciones de frontera:

• dp[0][j] = 1 (primera fila)
• dp[i][0] = 1 (primera columna)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

Complejidad temporal O(m·n). La solución usa la regla de la suma para conjuntos disjuntos de caminos.

Suma Mínima de Caminos: Minimizando el Costo de la Ruta

Dada una cuadrícula de m × n con números no negativos. Encuentra la suma mínima de valores en un camino desde (0,0) hasta (m-1,n-1) al moverse hacia la derecha o hacia abajo.

Un algoritmo voraz (elegir el mínimo local) falla—conduce a callejones sin salida con valores altos. Se requiere optimización global.

Define dp[i][j] como el costo mínimo para llegar a (i,j). Relación de recurrencia:

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Condiciones de frontera:

dp[0][0] = grid[0][0]
for j in range(1, n): dp[0][j] = grid[0][j] + dp[0][j-1]
for i in range(1, m): dp[i][0] = grid[i][0] + dp[i-1][0]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

Complejidad O(m·n). Cada valor se usa para todas las celdas posteriores.

Subir Escaleras: Números de Fibonacci en PD

Subir escaleras con n escalones (1 ≤ n ≤ 45), cada paso es de 1 o 2 escalones. Encuentra el número de formas.

Para n=1: 1 forma

n=2: 2 formas (1+1, 2)

n=3: 3 formas (1+1+1, 1+2, 2+1)

Relación de recurrencia:

dp[n] = dp[n-1] + dp[n-2]

Una recursión simple conduce a complejidad exponencial O(φ^n) debido a cálculos repetidos. Un arreglo de PD resuelve el problema:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

Una versión optimizada usa O(1) de memoria con dos variables.

Señales de Problemas de Programación Dinámica

Aplica PD cuando se cumplen dos condiciones:

• Subestructura óptima: la solución óptima consiste en soluciones óptimas a subproblemas.
• Subproblemas superpuestos: los mismos subproblemas se calculan múltiples veces.

| Problema | Subestructura Óptima | Subproblemas Superpuestos |

|--------|-------------------------|---------------------------|

| Caminos Únicos | Suma de caminos desde celdas adyacentes | Cada camino a una celda se superpone |

| Suma Mínima de Caminos | Costo mínimo desde vecinos | El costo se usa para todas las celdas abajo/derecha |

| Subir Escaleras | Suma desde n-1 y n-2 | Las llamadas recursivas se repiten |

Conclusiones Clave

• Relaciones de recurrencia definen la esencia de la PD: dp[i][j] depende solo de valores adyacentes ya calculados.
• Condiciones de frontera se llenan por separado para la primera fila/columna o casos base.
• Complejidad temporal es siempre O(tamaño de entrada) con una implementación tabular adecuada.
• Memoria se puede optimizar: para cuadrículas—una fila, para problemas lineales—dos variables.
• Combinatoria a menudo proporciona un atajo matemático, pero las soluciones algorítmicas son más importantes para entrevistas.

— Editorial Team