游戏说明
有一组数字,p1和p2轮流选择,最后达到一种状态定胜负。
用递归求解:
- p1开始游戏,遍历所有p1可选的可能。
- 如果剩下的游戏状态让p2开始,都是导致p2赢,则p1失败。
- 如果剩下的游戏状态让p2开始,有一个是p2失败,则p1赢。
def game(初始状态):
for i in set(剩余所有状态):
if game(剩余所有状态 - i) == False:
return True
# 遍历完所有可能状态,全为对手赢(True), 返回 输(False)
return False
例题:
https://leetcode.com/problems/can-i-win/#/description
https://leetcode.com/problems/predict-the-winner/#/description