Giả sử chúng ta có một danh sách các số được gọi là kẹo và hai người đang chạy đua để thu thập được nhiều kẹo nhất. Ở đây cuộc đua diễn ra theo lượt, người 1 xuất phát trước và trong mỗi lượt anh ta có thể nhặt kẹo từ phía trước hoặc từ phía sau. Chúng ta phải kiểm tra xem người 1 có thể thu thập nhiều kẹo hơn người khác hay không.
Vì vậy, nếu đầu vào là kẹo =[1, 4, 3, 8], thì đầu ra sẽ là Đúng, vì người 1 có thể lấy 8 viên kẹo trong vòng đầu tiên và bất kể người thứ hai chọn 1 hay 3, người 1 có thể giành chiến thắng bằng cách lấy bất kỳ viên kẹo nào còn lại.
Để 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 kẹo
-
Xác định sự khác biệt của hàm (). Thao tác này sẽ sang trái, sang phải
-
nếu bên trái giống bên phải, thì
-
trả lại kẹo [trái]
-
-
trả về tối đa (kẹo [trái] - chênh lệch (trái + 1, phải)) và (kẹo [phải] - chênh lệch (trái, phải - 1))
-
từ phương thức chính, hãy làm như sau -
-
trả về true khi chênh lệch (0, N - 1)> 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ụ
class Solution: def solve(self, candies): N = len(candies) def difference(left, right): nonlocal candies if left == right: return candies[left] return max(candies[left] − difference(left + 1, right), candies[right] − difference(left, right − 1)) return difference(0, N − 1) > 0 ob = Solution() candies = [1, 4, 3, 8] print(ob.solve(candies))
Đầu vào
[1, 4, 3, 8]
Đầu ra
True