Giả sử có hai người chơi Amal và Bimal, họ đang chơi một trò chơi và với Amal thì bắt đầu trước. Ban đầu, có n viên đá khác nhau trong một đống. Trên mỗi lượt của người chơi, anh ta thực hiện một động tác bao gồm loại bỏ bất kỳ số hình vuông (khác 0) của đá khỏi đống. Ngoài ra, nếu một người chơi không thể di chuyển, anh ta sẽ thua trò chơi. Vì vậy, nếu chúng ta có n, chúng ta phải kiểm tra xem Amal có thể thắng trò chơi hay không.
Vì vậy, nếu đầu vào là n =21, thì đầu ra sẽ là True vì lúc đầu Amal có thể lấy 16, sau đó Bimal lấy 4, sau đó Amal lấy 1 và thắng trò chơi.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Square:=một danh sách mới
-
hình vuông:=1
-
tăng:=3
-
trong khi hình vuông <=n, làm
-
chèn hình vuông vào cuối các hình vuông
-
vuông:=vuông + tăng
-
tăng:=tăng + 2
-
-
chèn hình vuông vào cuối các hình vuông
-
dp:=một danh sách trống có kích thước (n + 1)
-
dp [0]:=Sai
-
đối với k trong phạm vi từ 1 đến n, thực hiện
-
s:=0
-
dp [k]:=Sai
-
trong khi các ô vuông [s] <=k và dp [k] trống, hãy thực hiện
-
nếu dp [k - square [s]] trống, thì
-
dp [k]:=Đúng
-
-
s:=s + 1
-
-
-
trả về phần tử cuối cùng của dp
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn
def solve(n):
squares = []
square = 1
increase = 3
while square <= n:
squares.append(square)
square += increase
increase += 2
squares.append(square)
dp = [None] * (n + 1)
dp[0] = False
for k in range(1, n + 1):
s = 0
dp[k] = False
while squares[s] <= k and not dp[k]:
if not dp[k - squares[s]]:
dp[k] = True
s += 1
return dp[-1]
n = 21
print(solve(n)) Đầu vào
21
Đầu ra
True