# 5 Ejemplos de memoización en Python: #1. Secuencia de Fibonacci usando memoización: def fibonacci(n, memo={}): if n in memo: return memo[n] if n <= 2: return 1 memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo) return memo[n] #2. Factorial usando memoización: def factorial(n, memo={}): if n in memo: return memo[n] if n == 0: return 1 memo[n] = n * factorial(n-1, memo) return memo[n] #3. Calcula la n-ésima potencia de un número usando memoización: def power(x, n, memo={}): if n == 0: return 1 if n % 2 == 0: if n not in memo: memo[n] = power(x, n/2, memo) return memo[n] * memo[n] else: if (n-1) not in memo: memo[n-1] = power(x, (n-1)/2, memo) return x * memo[n-1] * memo[n-1] #4. Subsecuencia común más larga usando memoización: def lcs(s1, s2, memo={}): if (s1, s2) in memo: return memo[(s1, s2)] if not s1 or not s2: return "" if s1[0] == s2[0]: memo[(s1, s2)] = s1[0] + lcs(s1[1:], s2[1:], memo) else: memo[(s1, s2)] = max(lcs(s1[1:], s2, memo), lcs(s1, s2[1:], memo), key=len) return memo[(s1, s2)] #5. Problema de mochila usando memoización: def knapsack(capacity, weights, values, n, memo={}): if (capacity, n) in memo: return memo[(capacity, n)] if n == 0 or capacity == 0: return 0 if weights[n-1] > capacity: memo[(capacity, n)] = knapsack(capacity, weights, values, n-1, memo) return memo[(capacity, n)] memo[(capacity, n)] = max(values[n-1] + knapsack(capacity-weights[n-1], weights, values, n-1, memo), knapsack(capacity, weights, values, n-1, memo)) return memo[(capacity, n)]