algorithm - 动态规划纸牌游戏

Question

请检查我遇到的这个问题:

“你和你八岁的侄子埃尔莫决定玩一个简单的纸牌游戏。一开始在游戏中，牌面朝上排成一排。每张卡值不同的数字点数。发完所有牌后，您和 Elmo 轮流移除最左边或从一排最右边的牌开始，直到所有的牌都消失了。在每个回合中，您可以决定拿两张牌。游戏的获胜者是收集最多积分的玩家当游戏结束时。从来没有上过算法课，Elmo 遵循明显的贪心策略？轮到他时，Elmo 总是拿到点数较高的牌。你的任务是找到一个策略只要有可能，它就会击败 Elmo。 (像这样打一个 child 子似乎很卑鄙，但是Elmo 绝对讨厌大人让他赢。)

描述并分析一种算法，以确定在给定初始卡片序列的情况下，与 Elmo 对战可以收集的最大积分。”

我已经完成了这个问题的大部分理论工作。例如，我已经完成了 DP 所需的 optimus 子结构演示，并且我已经定义了递归低效形式，它解释了游戏是如何完成的。现在下一步是设计一个自下而上的算法来有效地解决这个问题，或者，如果它可能有帮助，一个自上而下的内存解决方案。我就是做不到其中任何一个。你会如何解决这个问题？

Answer 1

算法简单，可以这样使用记忆化和动态规划:

def findMax(mem, cards, myTurn):
    maxValue = 0
    if(not cards):
        return 0
    if str(cards) in mem: #If we have already compute this state
        return mem[str(cards)]
    elif not myTurn: #turn of Elmo
        if cards[0] > cards[len(cards) - 1]:
            maxValue = findMax(mem, cards[1:], True)
        else:
            maxValue = findMax(mem, cards[:-1], True)
    else: #your turn
        maxValue = max(cards[0] + findMax(mem, cards[1:], False), cards[len(cards) - 1] + findMax(mem, cards[:-1], False))
    mem[str(cards)] = maxValue  #Store the max value for this state
    return maxValue

import random
size = int(10 + random.randint(0,1))
cards = [random.randint(0,50) for x in range(size)]
print "Cards" + str(cards)
print findMax({}, cards, True)

输出:

Cards: [28, 33, 48, 0, 26, 1, 3, 11, 22, 32, 12]
Max value: 120