¿Cómo convertir esta solución recursiva memoizada en una solución iterativa “bottom-up”?
Tengo una solución para un problema que utiliza programación dinámica. Necesito ayuda para convertir esto de una solución recursiva a una iterativa.
La función recibe un número y sigue las tres reglas:
1. puede dividir el número por la mitad
2. puede restar uno
3. puede sumar uno
hasta que el número sea 1. Mi objetivo es encontrar el número mínimo de pasos que se necesitan para hacer esto.
Aquí está mi solución:
def solution(n):
n = int(n)
memo = {}
return memoized fuel injection perfection(n, memo)
def memoized fuel injection perfection(n, memo):
if n == 1:
return 0
if n == 2:
return 1
if n in memo:
return memo[n]
if n % 2 == 0:
if n not in memo:
memo[n] = memoized fuel injection perfection(n//2, memo) + 1
return memo[n]
return min(memoized fuel injection perfection(n-1, memo), memoized fuel injection perfection(n+1, memo)) + 1
Pero cuando ingreso números mayores a 300 dígitos, obtengo un error recursivo. ¿Cómo puedo convertir esto en una solución iterativa? Cualquier ayuda o guía es apreciada.
Aquí hay una solución iterativa que creé, pero estoy obteniendo un MemoryError con entradas muy grandes. ¿Hay alguna forma en que pueda optimizar el almacenamiento de las variables para no tener que calcularlas para cada número?
def solution(n):
memo = {}
memo[0] = 0
memo[1] = 0
memo[2] = 1
n = int(n)
for i in range(3, n+1):
if i % 2 == 0:
memo[i] = memo[i//2] + 1
else:
memo[i] = min(memo[i//2], memo[i//2 + 1]) + 2
return memo[n]
davy.ai
Para optimizar la solución iterativa y evitar MemoryError para entradas muy grandes, podemos utilizar un enfoque de ventana deslizante para realizar un seguimiento únicamente de los tres números anteriores en lugar de almacenar todos los números anteriores en el diccionario memo. Aquí está la solución iterativa optimizada:
En este enfoque, solo realizamos un seguimiento de los tres números anteriores en el diccionario memo. Inicializamos memo[1], memo[2] y memo[3] como 0, 1 y 2 respectivamente. Luego, para cada número i desde 4 hasta n, aplicamos la misma lógica que antes: si i es par, memo[i] = memo[i//2] + 1, y si i es impar, memo[i] = min(memo[i//2], memo[i//2 + 1]) + 2. Sin embargo, también verificamos si i es divisible por 3 y, si lo es, comparamos memo[i] con memo[i//3] + 1 y tomamos el mínimo de los dos. Esto tiene en cuenta la tercera regla de que la función puede dividir el número por 3.
Utilizando este enfoque de ventana deslizante, reducimos el uso de memoria y evitamos MemoryError para entradas muy grandes.