python递归算法_python – 如何加速递归算法
我正在尝试解决Hackerrank challenge
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)
该算法本质上是minimax算法,因为它看起来向前移动然后递归调用相同的函数.问题是在Hackerrank中,它因超时而终止：
实际上,我注意到评估which_player_wins(40)已经需要约2秒.对于更快解决方案的任何想法都不会超时？
