动态规划算法练习 (2)

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必赢。 因为：

1. 最后一步中，拿到2的一定会赢，拿到1的会输。
2. 当N为奇数时，其约数一定是奇数，所以Bob拿到的一定会是偶数，Bob拿1，这样Alice拿到的还是奇数，这样一直到Bob拿到2，Alice就会输掉。
3. 当N为偶数时，偶数的约数可奇可偶，Alice可以选1或者一个奇数，Bob拿到的就是一个奇数，从上面可知奇数必输。Alice则会赢。

所以此题就会转化为一个数学问题：

def divisorgame(N):
    return N % 2 == 0

2. 三步问题 (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]。值得注意的是这里在结果取模会导致超时，需要在过程中就取模。

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)%1000000007
        return right