1. Divisor Game ( https://leetcode-cn.com/problems/divisor-game )

Alice and Bob play games together, and they take turns. Alice started the game first. Initially, there was a number N on the blackboard. In each player's round, the player needs to perform the following operations: Pick any x that satisfies 0 <x <N and N% x == 0. Replace the number N on the blackboard with N-x. If the player cannot perform these operations, they will lose the game. Return True only when Alice wins the game, otherwise it returns false. Assume that both players participate in the game at their best.

• Dynamic programming can be analyzed step by step to find the rule: When N = 1, Alice has no choice and loses; When N = 2, Alice chooses 1, Bob has no choice and wins. When N=3, Alice chooses 1, and Bob chooses N=2. According to the previous result, he wins first, so Bob wins and Alice loses. When N=4, Alice chooses 1, and Bob chooses N=3. According to the previous result, Bob will lose first and Alice will win. …… By analogy, it can be seen that if alice chooses k, then N%k==0 and must lose when Nk (that is, when Bob must lose) these two conditions must be met.

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): # actual value of 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]

• Mathematical induction. The above dynamic induction method requires two layers of loops, which is less efficient. If you analyze this problem carefully, there are additional solutions. Looking at the result, you can find that when N is odd, Alice (first move) must lose; when N is even, Alice must win. because:

1. In the last step, those who get 2 will definitely win, and those who get 1 will lose.
2. When N is an odd number, its divisor must be an odd number, so Bob will get an even number, and Bob will get 1, so Alice will get an odd number, so until Bob gets 2, Alice will lose.
3. When N is an even number, the divisor of the even number can be odd or even, Alice can choose 1 or an odd number, and what Bob gets is an odd number. From the above, we know that the odd number must lose. Alice will win.

So this question will be transformed into a mathematical question:

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

2. Three-step problem ( https://leetcode-cn.com/problems/three-steps-problem-lcci/ )

Three-step question. A child is going up the stairs. The stairs have n steps. The child can go up 1, 2, or 3 steps at a time. Implement a method to calculate how many ways the child has to go up the stairs. The result may be very large, you need to modulo 1000000007 to the result.

This is basically the same as the stair climbing problem written last time, and the solution is also the same. The state transition equation is dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. It is worth noting that modulo the result here will cause a timeout, and the modulo needs to be taken during the process.

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