Giả sử hai người chơi đang chơi một trò chơi. Trường hợp một số viên kẹo được đặt trên một dòng, và người 1 được đưa ra một danh sách các số được gọi là num thể hiện giá trị điểm của mỗi viên kẹo. Vào lượt của mỗi người, họ có thể chọn 1, 2 hoặc 3 viên kẹo từ đầu hàng, sau đó xóa chúng khỏi danh sách và lấy tổng điểm của họ được cộng vào điểm của họ. Trò chơi này sẽ kết thúc khi xóa hết số kẹo và người có số điểm cao hơn sẽ là người chiến thắng. Chúng ta phải kiểm tra xem người số 1 có thể thắng trò chơi này hay không.
Vì vậy, nếu đầu vào là nums =[1, 1, 2, 3, 50], thì đầu ra sẽ là True, vì người 1 có thể lấy 1 viên kẹo, thì người chơi kia phải lấy 1, 2 hoặc 3 viên kẹo. Trong mọi trường hợp, người 1 có thể lấy kẹo có giá trị là 50.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
n:=kích thước của nums
-
table:=một mảng có ba số 0.
-
đối với tôi trong phạm vi n - 1 đến 0, giảm 1, thực hiện
-
lợi nhuận:=−inf
-
sum_val:=0
-
đối với j trong phạm vi i đến tối thiểu là i + 3 và n, thực hiện
-
sum_val:=sum_val + nums [j]
-
lợi nhuận:=tối đa lợi nhuận và (sum_val - table [j - i])
-
-
set table:=một danh sách có ba giá trị [lợi nhuận, table [0], table [1]]
-
-
trả về true khi table [0]> 0, ngược lại là false
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
import math class Solution: def solve(self, nums): n = len(nums) table = [0, 0, 0] for i in range(n − 1, −1, −1): profit = −math.inf sum_val = 0 for j in range(i, min(i + 3, n)): sum_val += nums[j] profit = max(profit, sum_val − table[j − i]) table[:] = [profit, table[0], table[1]] return table[0] > 0 ob = Solution() nums = [1, 1, 2, 3, 50] print(ob.solve(nums))
Đầu vào
[1, 1, 2, 3, 50]
Đầu ra
True