python - 如何加速递归算法

Question

我正在尝试解决 Hackerrank 挑战 Game of Stones ，下面复制了一个(缩短的)问题陈述。

我想出了以下解决方案:

# The lines below are for the Hackerrank submission
# T = int(raw_input().strip())
# ns = [int(raw_input().strip()) for _ in range(T)]

T = 8
ns = [1, 2, 3, 4, 5, 6, 7, 10]

legal_moves = [2, 3, 5]

def which_player_wins(n):
    if n <= 1:
        return "Second"               # First player loses
    elif n in legal_moves:
        return "First"                # First player wins immediately
    else:
        next_ns = map(lambda x: n - x, legal_moves)
        next_ns = filter(lambda x: x >= 0, next_ns)
        next_n_rewards = map(which_player_wins, next_ns)      # Reward for opponent
        if any(map(lambda x: x=="Second", next_n_rewards)):            # Opponent enters a losing position
            return "First"
        else:
            return "Second"

for n in ns:
    print which_player_wins(n)

该算法本质上是极小极大算法，因为它向前看一步，然后递归调用相同的函数。问题是在 Hackerrank 中，它因超时而终止:

事实上，我注意到评估 which_player_wins(40) 已经花费了大约 2 秒。有没有关于更快且不会超时的解决方案的想法？

Answer 1

从问题描述看来，您可以保留每次计算的中间结果和最终结果，以供以后计算使用。如果是这样，递归算法就不是最优的。相反，请使用动态编程风格。

换句话说，保留一个全局数组，用于存储先前确定输赢的结果。当您确定 n 的新值时，不要一直递归到最后，而是使用之前的确定。

例如，当您到达 n=10 时，您会看到第一个玩家移除 3 个棋子剩下 7 个棋子，您已经将其视为第二个玩家的胜利。因此，第一个玩家获得 10 个棋子即获胜。

我相信您的递归算法会重新计算 n=7 的结果，而不是使用之前的工作。