Jogo de moedas

Question

Considere uma fileira de n moedas de valores \(v(1) ... v (n)\), onde \(n\) é par. Jogamos um jogo contra um oponente alternando lances. Em cada turno, um jogador seleciona a primeira ou a última moeda da linha, remove-a da linha permanentemente e recebe o valor da moeda. Determinar a quantidade máxima possível de dinheiro que pode se ganhar se nós nos movemos primeiro. Resolva esse problema usando programação dinâmica e apresente um pseudo-code. Qual a complexidade computacional dessa solução?

Answer 1

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))