Hai người đua lấy kẹo từ danh sách candies. Luân phiên, người 1 đi trước, mỗi lượt lấy từ đầu hoặc cuối danh sách. Kiểm tra người 1 có thể lấy nhiều kẹo hơn người 2 không.
Ví dụ: candies = [1, 4, 3, 8] → True (người 1 lấy 8, bất kể người 2 lấy gì, người 1 thắng).
Giải pháp
Đệ quy với memo (hoặc DP): difference(left, right) = hiệu số điểm người hiện tại có thể đạt được hơn đối thủ trên đoạn [left, right].
- Nếu left == right: trả về candies[left]
- Ngược lại: max(candies[left] - difference(left+1, right), candies[right] - difference(left, right-1))
- Người 1 thắng nếu difference(0, n-1) > 0
Ví dụ minh họa
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