Zagrajmy w grę:

Są n stosy monet z rzędu. i -ty ​​stos składa się z monet d_i. Dwóch graczy: Gracz 1, Gracz 2 wykonują ruchy naprzemiennie. Gracz w swojej turze może wziąć tylko pierwszy stos lub ostatni stos lub oba. Gra kończy się, gdy nie ma już monet. Każdy gracz chce mieć na końcu tyle monet, ile to możliwe. Rozpoczyna się gracz1.

Zastanawiałem się nad algorytmem (brzmi jak chciwy algorytm), aby policzyć, ile monet każdy gracz ma na końcu gry, gdy obie grają optymalnie.

Nie mam pojęcia, jak podejść do takich algorytmów. Tylko zgadnij strategię lub jest jakiś sposób, aby to wydedukować? A może to zbyt dziwny problem, aby zaimplementować algorytm?

Przykłady (monety w stosach od pierwszego do n-tego):

1, 100, 1 - gracze mają odpowiednio 2 i 100 monet (niestety pierwszy gracz może wziąć tylko pierwszy i ostatni stos - drugi gracz zawsze bierze stos ze 100 monet)

1, 1, 100, 1, 1, 5 - gracze mają odpowiednio 8 i 101 monet (myślę, że to jest po optymalnej grze - najpierw weź 5 i 1, a potem drugi weź 1, aby zapobiec temu, że gracz1 zabrał stos 100 monet. Jeśli gracz1 weź pierwszy mniej niż 6 monet, zawsze będzie miał mniej niż 8 monet).

Mam nadzieję, że podałem wystarczająco problem. Czy zgadzasz się, że jest to interesujące? :) Czy ktoś może pomóc?