DP bottom-up con tabulación
Convierta soluciones top-down en tablas de DP iterativas y reduzca el espacio de O(n) a O(1) cuando solo se necesiten las últimas entradas.
DP bottom-up con tabulación es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 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.
DP de abajo arriba: el enfoque de tabulación
La DP de abajo arriba (tabulación) rellena una tabla con las respuestas de los subproblemas, comenzando por los más pequeños y construyendo progresivamente la respuesta. En lugar de descender mediante recursión y almacenar resultados al volver, calcula de forma iterativa desde los casos base. La tabla suele ser un array 1D o 2D en el que cada celda se calcula a partir de celdas ya rellenadas. Esto elimina por completo la recursión: no hay pila de llamadas ni límite de recursión, y mejora la localidad de caché.
# Converting top-down to bottom-up:
# Top-down: start at fib(n), recurse to smaller, cache
# Bottom-up: start at fib(0), fill table to fib(n)
# Key question for bottom-up:
# 'In what order do I fill the table so that when I compute dp[i],
# all values dp[i] depends on are already filled?'
# For Fibonacci: dp[i] needs dp[i-1] and dp[i-2]
# Fill order: i = 2, 3, 4, ..., n (left to right)
print('Bottom-up: fill small sub-problems first, build to answer')Fibonacci de abajo arriba
La versión de Fibonacci de abajo arriba rellena dp[0..n] de izquierda a derecha. dp[i] = dp[i-1] + dp[i-2] para i >= 2. Los casos base son dp[0] = 0 y dp[1] = 1, almacenados directamente en el array. El tiempo es O(n) y el espacio es O(n) para la tabla completa. Cuando observe que dp[i] solo depende de los dos últimos valores, puede reducir el espacio a O(1) con dos variables; este es el paso de optimización del espacio.
def fib_bottom_up(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0 # base case
dp[1] = 1 # base case
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print([fib_bottom_up(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# Space-optimised to O(1):
def fib_optimised(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(fib_optimised(50)) # 12586269025Cambio de monedas de abajo arriba
Para el cambio de monedas, la tabla de abajo arriba es dp[0..amount], donde dp[i] = número mínimo de monedas para obtener la cantidad i. Inicialice dp[0] = 0 (cero monedas para una cantidad cero) y dp[1..amount] = infinity. Para cada cantidad i de 1 a target, pruebe cada moneda: si i >= coin, entonces dp[i] = min(dp[i], 1 + dp[i - coin]). La respuesta es dp[amount], o -1 si sigue siendo infinity.
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins for amount 0
for i in range(1, amount + 1):
for coin in coins:
if i >= coin: # can use this coin
dp[i] = min(dp[i], 1 + dp[i - coin])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change([1, 5, 6, 9], 11)) # 2: (5+6)
print(coin_change([2], 3)) # -1: impossible
print(coin_change([1, 2, 5], 11)) # 3: 5+5+1
print(coin_change([186, 419, 83, 408], 6249)) # 20Orden de llenado: la idea fundamental
El orden de llenado es el corazón de la DP de abajo arriba. Para cualquier estado dp[i], primero deben calcularse todos los estados de los que depende. En una DP 1D donde dp[i] depende de dp[i-1] y dp[i-2], rellene de izquierda a derecha. En una DP 2D donde dp[i][j] depende de dp[i-1][j] y dp[i][j-1], rellene fila por fila (de arriba abajo y de izquierda a derecha). Dibuje siempre las flechas de dependencia antes de escribir el código para confirmar el orden de llenado.
# Fill order examples:
# 1D: dp[i] = f(dp[i-1], dp[i-2])
# Arrows point LEFT: fill LEFT TO RIGHT
# i: 0 -> 1 -> 2 -> ... -> n
# 2D: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# Arrows point LEFT and UP: fill TOP-LEFT TO BOTTOM-RIGHT
# Fill row 0 first, then row 1, etc.
# 2D reversed: dp[i][j] = f(dp[i+1][j], dp[i][j+1])
# Arrows point RIGHT and DOWN: fill BOTTOM-RIGHT TO TOP-LEFT
# Used in interval DP and some string problems
print('Draw dependencies first, then determine fill order')LCS de abajo arriba: tabla 2D
La tabla de abajo arriba de la subsecuencia común más larga es de (m+1) × (n+1), donde dp[i][j] = LCS de s1[:i] y s2[:j]. Casos base: dp[0][j] = dp[i][0] = 0 (una cadena vacía tiene una LCS de longitud 0 con cualquier cadena). Rellene fila por fila: si s1[i-1] == s2[j-1], dp[i][j] = 1 + dp[i-1][j-1]; en caso contrario, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). La respuesta es dp[m][n].
def lcs_bottom_up(s1, s2):
m, n = len(s1), len(s2)
# (m+1) x (n+1) table, initialised to 0
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]: # characters match
dp[i][j] = 1 + dp[i-1][j-1]
else: # skip one character
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lcs_bottom_up('abcde', 'ace')) # 3
print(lcs_bottom_up('ABCBDAB', 'BDCAB')) # 4: 'BCAB' or 'BDAB'Optimización del espacio: array deslizante
Muchas tablas de DP 2D pueden reducirse a 1D (o a 2 filas) observando que dp[i][j] solo depende de la fila actual y de la fila anterior. Mantenga dos arrays: prev y curr, o actualice un único array en el orden correcto. En LCS, dp[i][j] depende de dp[i-1][j], dp[i][j-1] y dp[i-1][j-1]; basta con conservar la fila anterior.
def lcs_space_optimised(s1, s2):
m, n = len(s1), len(s2)
# Keep only one row (previous row state)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if s1[i-1] == s2[j-1]:
curr[j] = 1 + prev[j-1] # dp[i-1][j-1]
else:
curr[j] = max(prev[j], curr[j-1]) # dp[i-1][j] and dp[i][j-1]
prev = curr
return prev[n]
print(lcs_space_optimised('abcde', 'ace')) # 3
# Space: O(n) instead of O(mn)Robar casas de abajo arriba
La solución de abajo arriba para robar casas rellena dp[0..n-1], donde dp[i] = beneficio máximo al robar casas desde la 0 hasta la i. dp[0] = nums[0], dp[1] = max(nums[0], nums[1]) y, para i >= 2: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Como dp[i] solo depende de los dos últimos valores, esto permite optimizar inmediatamente el espacio a O(1) con dos variables, un patrón habitual en DP 1D con dependencias de dos pasos.
def rob_bottom_up(nums):
if not nums: return 0
if len(nums) == 1: return nums[0]
# Full table version: O(n) space
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
def rob_optimised(nums):
# O(1) space: only need last two values
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
prev2, prev1 = prev1, max(prev1, prev2 + nums[i])
return prev1
print(rob_optimised([2, 7, 9, 3, 1])) # 12Suma mínima de una ruta en una cuadrícula
Suma mínima de una ruta (LeetCode #64): encuentre una ruta desde la esquina superior izquierda hasta la inferior derecha que minimice la suma de los valores (solo puede moverse a la derecha o hacia abajo). DP 2D: dp[i][j] = suma mínima para llegar a la celda (i,j). dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Rellene de izquierda a derecha y de arriba abajo. Caso base: dp[0][0] = grid[0][0]; la primera fila se rellena moviéndose solo a la derecha y la primera columna, moviéndose solo hacia abajo.
def min_path_sum(grid):
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
# Fill first row (can only come from left)
for c in range(1, cols):
dp[0][c] = dp[0][c-1] + grid[0][c]
# Fill first column (can only come from above)
for r in range(1, rows):
dp[r][0] = dp[r-1][0] + grid[r][0]
# Fill rest of the table
for r in range(1, rows):
for c in range(1, cols):
dp[r][c] = grid[r][c] + min(dp[r-1][c], dp[r][c-1])
return dp[rows-1][cols-1]
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum(grid)) # 7: 1+3+1+1+1Modificar la tabla de DP directamente
Cuando no se permite espacio adicional, a veces puede modificar la propia cuadrícula de entrada para utilizarla como tabla de DP. Para la suma mínima de una ruta, sobrescriba grid[i][j] con el coste mínimo para llegar a esa celda. Esto usa O(1) de espacio adicional, pero destruye la entrada; mencione siempre esta compensación al entrevistador y confirme que es aceptable. Si debe conservar la entrada, use el enfoque de array deslizante.
def min_path_sum_inplace(grid):
rows, cols = len(grid), len(grid[0])
# Modify grid in-place (O(1) extra space, destroys input)
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue # starting cell
elif r == 0:
grid[r][c] += grid[r][c-1] # first row
elif c == 0:
grid[r][c] += grid[r-1][c] # first column
else:
grid[r][c] += min(grid[r-1][c], grid[r][c-1])
return grid[rows-1][cols-1]
import copy
grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_inplace(copy.deepcopy(grid))) # 7Comparación de top-down y bottom-up en Coin Change
Ambos enfoques resuelven Coin Change de forma óptima, pero difieren en la práctica. Top-down es más limpio de escribir y solo calcula los subproblemas que realmente son alcanzables. Bottom-up calcula todas las cantidades desde 0 hasta el objetivo, incluso aquellas que no se pueden alcanzar con las monedas disponibles (que permanecen en infinito). Para problemas dispersos (con pocos estados alcanzables), top-down es más eficiente; para problemas densos, bottom-up tiene una sobrecarga menor.
import functools
# Top-down: only computes reachable amounts
def coin_change_top(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0: return 0
if rem < 0: return float('inf')
return 1 + min(dp(rem - c) for c in coins)
r = dp(amount)
return r if r != float('inf') else -1
# Bottom-up: computes all amounts 0 to target
def coin_change_bottom(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if i >= c: dp[i] = min(dp[i], 1 + dp[i-c])
return dp[amount] if dp[amount] != float('inf') else -1
print(coin_change_top([1,5,6,9], 11)) # 2
print(coin_change_bottom([1,5,6,9], 11)) # 2Unique Paths: DP 2D clásica
Unique Paths (LeetCode #62) cuenta el número de rutas desde la esquina superior izquierda hasta la esquina inferior derecha de una cuadrícula de m×n, moviéndose únicamente hacia la derecha o hacia abajo. La recurrencia es sencilla: dp[i][j] = dp[i-1][j] + dp[i][j-1] — las rutas desde arriba más las rutas desde la izquierda. Casos base: toda la primera fila y toda la primera columna tienen exactamente 1 ruta (solo hay una dirección posible). Esta DP 2D se completa en tiempo O(mn) y puede reducirse a un espacio O(n) mediante una fila deslizante.
def unique_paths(m, n):
# dp[i][j] = number of paths to reach cell (i,j)
dp = [[1] * n for _ in range(m)]
# Base: first row and first column are all 1
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]
print(unique_paths(3, 7)) # 28
print(unique_paths(3, 2)) # 3
# O(n) space rolling row:
def unique_paths_opt(m, n):
row = [1] * n
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j-1]
return row[n-1]
print(unique_paths_opt(3, 7)) # 28Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: DP bottom-up con tabulación y cómo determinar el orden de llenado a partir de las flechas de dependencia, la optimización del espacio mediante arrays deslizantes (de O(mn) a O(n)) y el seguimiento con dos variables (de O(n) a O(1)), así como implementaciones bottom-up de Fibonacci, Coin Change, LCS, House Robber y Minimum Path Sum. A continuación resolveremos de principio a fin los problemas Coin Change y Min-Cost Staircase de coste mínimo.
Preguntas frecuentes
¿La lección «DP bottom-up con tabulación» es gratis?
Sí — el texto completo de «DP bottom-up con tabulación» 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 «DP bottom-up con tabulación»?
Convierta soluciones top-down en tablas de DP iterativas y reduzca el espacio de O(n) a O(1) cuando solo se necesiten las últimas entradas. 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 3 de 4.
¿Cuánto tiempo toma la lección «DP bottom-up con tabulación»?
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
- Reconocimiento de DP: subproblemas superpuestos
- DP top-down con memoización
- DP bottom-up con tabulación
- Cambio de monedas y escalera de coste mínimo