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.
def divisorgame(N): if N <= 1: return False else: dp = [False] * N dp = False dp = 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]
So this question will be transformed into a mathematical question:
def divisorgame(N): return N% 2 == 0
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