Python - Memoización
# 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)]