A solução do problema utilizou a estratégia Maximin.
Como há um número muito grande de chamadas recursivas à função valor, usamos memoization, ou seja, calculamos o resultado da função e armazenamos em um dicionário. Sempre que a função for chamada novamente com os mesmos parâmetros, o resultado já calculado anteriormente é fornecido.
No exemplo abaixo, o número de vezes em que a função valor é calculada cai de 21845 vezes para apenas 64 com o uso do memoization.
def memoization(func):
memo = {}
def helper(i, j):
if (i, j) not in memo:
memo[(i, j)] = func(i, j)
return memo[(i, j)]
return helper
def valor(moedas):
@memoization
def _valor(i, j):
if i >= j:
return 0
esquerda = moedas[i] + min(_valor(i + 2, j), _valor(i + 1, j - 1))
direita = moedas[j] + min(_valor(i, j - 2), _valor(i + 1, j - 1))
return max(esquerda, direita)
return _valor(0, len(moedas) - 1)
m = [1, 4, 3, 1, 3, 6, 2, 7, 4, 8, 12, 6, 23, 6]
print(valor(m))