Decode Ways y conteo de rutas
Resuelva decode-ways —mapeos de dígitos a letras— como una DP similar a Fibonacci y cuente después las rutas de una escalera con tamaños de paso variables.
Decode Ways y conteo de rutas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 4 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.
El problema Decode Ways
Decode Ways (LeetCode 91) asigna una cadena de dígitos a letras: 'A'=1, 'B'=2, ..., 'Z'=26. Dada una cadena de dígitos codificada, cuente el número de formas distintas de decodificarla. Por ejemplo, '12' se puede decodificar como 'AB' (1+2) o como 'L' (12), lo que da 2 formas. '226' puede ser 'BZ' (2+26), 'VF' (22+6) o 'BBF' (2+2+6), lo que da 3 formas. Los ceros iniciales hacen que algunas decodificaciones no sean válidas.
# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)
s = '226'
print('Decodings for', s, ':', 3) # Expected: 3Formulación de DP para Decode Ways
Sea dp[i] el número de formas de decodificar s[:i]. Casos base: dp[0] = 1 (cadena vacía, una forma) y dp[1] = 1 si s[0] != '0'; en caso contrario, 0. Transición: si s[i-1] != '0', sume dp[i-1] (decodificación de un solo dígito). Si 10 ≤ int(s[i-2:i]) ≤ 26, sume dp[i-2] (decodificación de dos dígitos). Esencialmente, se trata del patrón de Fibonacci con comprobaciones de validez.
def num_decodings(s):
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1 # empty prefix
dp[1] = 0 if s[0] == '0' else 1
for i in range(2, n + 1):
# Single digit decode
if s[i-1] != '0':
dp[i] += dp[i-1]
# Two digit decode
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]
print(num_decodings('12')) # 2
print(num_decodings('226')) # 3
print(num_decodings('06')) # 0La trampa del cero inicial
La parte más complicada de Decode Ways es gestionar los ceros. Un '0' por sí solo no se puede decodificar (ninguna letra corresponde al 0), por lo que, si s[i-1] == '0', no debe sumar dp[i-1]. Un '0' como segundo dígito solo es válido si el número de dos dígitos es 10 o 20. '30' o '40' (y cualquier número superior) no son válidos porque superan 26. Compruebe siempre 10 ≤ two_digit ≤ 26, no solo two_digit ≤ 26.
def num_decodings(s):
if not s or s[0] == '0': return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # s[0] != '0' guaranteed by guard above
for i in range(2, n + 1):
one = int(s[i-1])
two = int(s[i-2:i])
if one != 0: dp[i] += dp[i-1] # valid single digit
if 10 <= two <= 26: dp[i] += dp[i-2] # valid two digits
return dp[n]
print(num_decodings('10')) # 1 (only 'J')
print(num_decodings('30')) # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100')) # 0 (dp[2]=1 then '00' invalid, single '0' invalid)Decode Ways con optimización de espacio
Al igual que en Fibonacci, la recurrencia de Decode Ways solo retrocede dos posiciones, por lo que puede reducir el espacio de O(n) a O(1) utilizando dos variables. Use prev2 (dos pasos atrás) y prev1 (un paso atrás). En cada paso, calcule curr a partir de ambas y, después, desplácelas. Es idéntico a la optimización de Fibonacci → dos variables.
def num_decodings_o1(s):
if not s or s[0] == '0': return 0
prev2 = 1 # dp[0]
prev1 = 1 # dp[1]
for i in range(2, len(s) + 1):
curr = 0
if s[i-1] != '0':
curr += prev1
two = int(s[i-2:i])
if 10 <= two <= 26:
curr += prev2
prev2, prev1 = prev1, curr
return prev1
print(num_decodings_o1('226')) # 3
print(num_decodings_o1('12')) # 2
print(num_decodings_o1('0')) # 0Contar caminos en una escalera
Climbing Stairs (LeetCode 70) plantea la siguiente pregunta: ¿de cuántas formas puede subir n escalones si puede dar 1 o 2 pasos cada vez? Es exactamente la sucesión de Fibonacci: ways(n) = ways(n-1) + ways(n-2). ways(1)=1, ways(2)=2, ways(3)=3, ways(4)=5. Se generaliza cuando puede dar hasta k pasos: ways(n) = sum(ways(n-1), ..., ways(n-k)).
def climb_stairs(n):
if n <= 2: return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
for i in range(1, 8):
print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!Climbing Stairs con pasos variables
Cuando puede dar cualquier número de pasos de un conjunto determinado (por ejemplo, {1, 3, 5}), la recurrencia se convierte en dp[i] = sum(dp[i-k] for k in steps if i-k >= 0). Utilice una ventana deslizante de tamaño max(steps) para mejorar la eficiencia de memoria. Se trata de la variante de conteo de la mochila ilimitada: cada tamaño de paso se puede utilizar cualquier número de veces.
def count_ways(n, steps):
dp = [0] * (n + 1)
dp[0] = 1 # one way to stay at ground
for i in range(1, n + 1):
for step in steps:
if i >= step:
dp[i] += dp[i - step]
return dp[n]
# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2])) # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3])) # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)Coste mínimo para subir escaleras
Min Cost Climbing Stairs (LeetCode 746) asigna un coste a cada escalón y pide encontrar el coste mínimo para llegar a la parte superior. Desde el escalón i puede saltar a i+1 o a i+2. La recurrencia es dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Puede empezar en el escalón 0 o en el escalón 1. La respuesta es min(dp[n-1], dp[n-2]).
def min_cost_climbing(cost):
n = len(cost)
if n == 1: return cost[0]
dp = [0] * n
dp[0] = cost[0]
dp[1] = cost[1]
for i in range(2, n):
dp[i] = cost[i] + min(dp[i-1], dp[i-2])
return min(dp[-1], dp[-2]) # can start from step 0 or 1
print(min_cost_climbing([10, 15, 20])) # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1])) # 6Decode Ways II: dígito comodín
Decode Ways II (LeetCode 639) introduce el carácter comodín '*' que puede representar cualquier dígito del 1 al 9. Esto aumenta considerablemente el número de decodificaciones válidas. Un '*' aislado aporta 9 posibilidades (cualquiera de los dígitos del 1 al 9). Dos '*' juntos pueden formar 9×9 combinaciones de dos dígitos, pero solo son válidas las que son ≤ 26 (11-19 = 9 posibilidades, 21-26 = 6 posibilidades → 15 posibilidades para '**'). Se requiere un análisis cuidadoso de los casos.
def num_decodings_ii(s):
MOD = 10**9 + 7
prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
for i in range(1, len(s)):
curr = 0
c, p = s[i], s[i-1]
# Single digit
if c == '*': curr += 9 * prev1
elif c != '0': curr += prev1
# Two digits
if p == '*' and c == '*': curr += 15 * prev2 # 11-19(9) + 21-26(6)
elif p == '*': curr += (2 if c <= '6' else 1) * prev2
elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
else:
two = int(p + c)
if 10 <= two <= 26: curr += prev2
prev2, prev1 = prev1, curr % MOD
return prev1 % MOD
print(num_decodings_ii('*')) # 9
print(num_decodings_ii('1*')) # 18Conexión con Fibonacci
Tanto Decode Ways como Climbing Stairs son problemas de la familia de Fibonacci disfrazados. Cualquier DP en la que dp[i] dependa únicamente de dp[i-1] y dp[i-2] tiene una estructura similar a Fibonacci y se puede resolver con espacio O(1). Las comprobaciones de validez (dígitos cero, tamaños de paso) modifican qué transiciones están activas, pero no la estructura fundamental de retroceder dos posiciones. Reconocer esta familia a simple vista es un patrón valioso para ganar rapidez en las entrevistas técnicas.
# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself: dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs: dp[i] = dp[i-1] + dp[i-2]
# Decode ways: dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs: dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber: dp[i] = max(dp[i-1], nums[i] + dp[i-2])
# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1) # 89Contar caminos en una cuadrícula
Un problema de conteo relacionado plantea lo siguiente: dada una cuadrícula de m×n, ¿cuántos caminos únicos van de la esquina superior izquierda a la esquina inferior derecha si solo puede moverse a la derecha o hacia abajo? La respuesta es el coeficiente binomial C(m+n-2, m-1). La solución con DP rellena una tabla bidimensional en la que dp[i][j] = dp[i-1][j] + dp[i][j-1]. Es una versión bidimensional de la escalera de Fibonacci: cada celda es la suma de la celda superior y la situada a la izquierda.
def unique_paths(m, n):
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]
# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
return math.comb(m + n - 2, m - 1)
print(unique_paths(3, 7)) # 28
print(unique_paths_math(3, 7)) # 28
print(unique_paths(3, 3)) # 6Resumen de errores frecuentes en entrevistas
Errores frecuentes en Decode Ways: (1) olvidar que '0' por sí solo no es válido; compruebe siempre s[i-1] != '0' antes de sumar dp[i-1]. (2) Usar two_digit <= 26 sin comprobar two_digit >= 10; '07' no debe decodificarse como 'G'. (3) Devolver dp[n-1] en lugar de dp[n]; la tabla está indexada desde 1, por lo que dp[n] corresponde a la cadena completa. Compruebe siempre dos veces los índices de los arrays cuando la tabla de DP tiene un elemento más que la entrada.
# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
dp = [0] * (len(s) + 1)
dp[0] = dp[1] = 1
for i in range(2, len(s) + 1):
if s[i-1] != '0': dp[i] += dp[i-1]
two = int(s[i-2:i])
# BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
# Fix: require two >= 10
if 10 <= two <= 26: dp[i] += dp[i-2] # CORRECT
return dp[len(s)]
print(buggy_decode('06')) # 0 (correct, '0' alone invalid)
print(buggy_decode('07')) # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27')) # 1 (only 'BG', 27>26 so no two-digit)Comprobación rápida
Ponga a prueba 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 que Decode Ways sigue una recurrencia similar a Fibonacci, con condiciones de validez para las decodificaciones de un dígito (distinto de cero) y de dos dígitos (10-26), que Climbing Stairs y Min Cost Staircase son variantes puras de Fibonacci que se pueden resolver con espacio O(1), y que reconocer la familia de Fibonacci que retrocede dos posiciones ahorra mucho tiempo durante las entrevistas. A continuación, exploraremos la DP bidimensional con Unique Paths y Minimum Path Sum en cuadrículas.
Preguntas frecuentes
¿La lección «Decode Ways y conteo de rutas» es gratis?
Sí — el texto completo de «Decode Ways y conteo de rutas» 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 «Decode Ways y conteo de rutas»?
Resuelva decode-ways —mapeos de dígitos a letras— como una DP similar a Fibonacci y cuente después las rutas de una escalera con tamaños de paso variables. 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 4 de 4.
¿Cuánto tiempo toma la lección «Decode Ways y conteo de rutas»?
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
- House Robber: recurrencia de tomar u omitir
- Subarray máximo y subarray de producto máximo
- Word Break y segmentación de strings
- Decode Ways y conteo de rutas