1. 除数博弈 Divisor Game (https://leetcode-cn.com/problems/divisor-game)
爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作： 选出任一 x，满足 0 < x < N 且 N % x == 0 。 用 N - x 替换黑板上的数字 N 。 如果玩家无法执行这些操作，就会输掉游戏。 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 false。假设两个玩家都以最佳状态参与游戏。
- 动态规划 可以分析一步步地先分析一下，找一下其中规律： 当N = 1时，Alice没有选择，输； 当N = 2时，Alice选1，Bob没有选择， 赢。 当N = 3时，Alice选1，Bob选的时候N=2，根据上一个结果，先手赢，所以Bob赢，Alice输。 当N = 4时，Alice选1，Bob选的时候N=3，根据上一个结果，先手输，Bob会输，Alice赢。 …… 以此类推，可以看出，假如alice选的k，那么N%k==0和当N-k的时候必须输（即Bob的时候必输）这两个条件必须满足。
def divisorgame(N):
if N <= 1:
return False
else:
dp = [False] * N
dp[0] = False
dp[1] = True
for i in range(3, N 1): # N的实际取值
for j in range(1, i // 2 1):
if i % j == 0 and dp[i-1-j] == False:
dp[i-1] = True
break
return dp[-1]- 数学归纳 上面的动态归纳法需要两层循环，效率较低，仔细分析一下这个题，还有额外的解法。看一下结果，可以发现，当N为奇数时，Alice（先手）必输；当N为偶数时，Alice必赢。 因为：
- 最后一步中，拿到2的一定会赢，拿到1的会输。
- 当N为奇数时，其约数一定是奇数，所以Bob拿到的一定会是偶数，Bob拿1，这样Alice拿到的还是奇数，这样一直到Bob拿到2，Alice就会输掉。
- 当N为偶数时，偶数的约数可奇可偶，Alice可以选1或者一个奇数，Bob拿到的就是一个奇数，从上面可知奇数必输。Alice则会赢。
所以此题就会转化为一个数学问题：
代码语言：javascript复制def divisorgame(N):
return N % 2 == 02. 三步问题 (https://leetcode-cn.com/problems/three-steps-problem-lcci/)
三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
这个与上次写的爬楼梯问题基本完全一致，解法也一致，状态转移方程即dp[i] = dp[i-1] dp[i-2] dp[i-3]。值得注意的是这里在结果取模会导致超时，需要在过程中就取模。
代码语言：javascript复制def waysToStep(self, n: int) -> int:
left = 1
middle = 2
right = 4
if n == 1:
return left
elif n == 2:
return middle
elif n == 3:
return right
else:
for i in range(n-3):
left, middle, right = middle, right, (left middle right)00000007
return right
