В игре с P1 и P2 существует N рядов монет (пронумерованных от 1 до N). Количество монет в каждом ряду дается вместе с определенным значением каждой монеты.
Чередование ходов P1 и P2;P1 играет первым.
В каждом ходу текущий игрок может выбрать одну строку, в которой все еще содержатся монеты, и взять одну из монет, оставшихся в этой строке. P1 может взять только первую (самую левую) оставшуюся монету в выбранной строке, в то время как P2 может взять только последнюю (самую правую) оставшуюся монету в выбранной строке. Игра заканчивается, когда не осталось монет.
Каждый игрок хочет максимизировать сумму достоинств полученных им монет. Предполагая, что оба P1 и P2 играют оптимально, какую максимальную сумму денег (сумму значений монет) P1 может заработать в этой игре?
Я попытался реализовать подход динамического программированияпосле некоторых онлайн-исследований.
Я запускаю цикл:
в каждом цикле первый P1 проверяет все первые значения монет в каждом стеке, выбирает максимум и добавляет егопеременная
то же самое относится и к P2, но она проверяет все последние значения монет в каждом стеке и выбирает максимальное значение
, в конце я получаю свой результат.
Но этот подход нене работает эффективно, так как N очень большой
Example :
N=2
Pile 1 - 5 2 3 4
Pile 2 - 1 6
Expected output:- 8
Explanation:-P1 takes the coin with value 5,
P2 takes 4,
P1 takes 2,
P2 takes 3,
P1 takes 1 and P2 takes 6.
At the end, P1 has 5+2+1=8 units of money.