如何加速递归算法

Question

我正在尝试解决Hackerrank挑战石头游戏,一个(缩短的)问题陈述在下面复制.

我提出了以下解决方案:

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

该算法本质上是minimax算法,因为它看起来向前移动然后递归调用相同的函数.问题是在Hackerrank中,它因超时而终止:

实际上,我注意到评估which_player_wins(40)已经需要大约2秒钟.对于更快解决方案的任何想法都不会超时？

Answer 1

从问题描述中可以看出,您可以保留每个计算的中间结果和最终结果,以便在以后的计算中使用.如果是这样,则递归算法不是最佳的.相反,使用动态编程风格.

换句话说,保留一个全局数组,用于存储先前确定的胜负的结果.当您确定新值时n,而不是一直到最后一次递归,请使用先前的确定.

例如,当你到达时n=10,你会看到第一个移除3块石头的玩家留下了7块石头,你已经看到它是第二个玩家的胜利.因此,10个宝石是第一个玩家的胜利.

我相信你的递归算法会重新计算结果,n=7而不是使用以前的工作.