Hai người chơi trò chơi: dãy kẹo với giá trị nums. Mỗi lượt lấy 1, 2 hoặc 3 kẹo từ đầu dãy, cộng điểm. Kết thúc khi hết kẹo, người điểm cao hơn thắng. Kiểm tra người 1 có thể thắng không.
Ví dụ: nums = [1, 1, 2, 3, 50] → True (người 1 lấy 1, buộc người 2 lấy 1-3 cái, người 1 lấy 50).
Giải pháp
DP từ cuối về đầu, table[3] lưu lợi thế tối đa từ vị trí i:
- table = [0, 0, 0] (lợi thế tại i, i+1, i+2)
- Duyệt i từ n-1 về 0:
- profit = -inf, sum_val = 0
- Thử lấy 1, 2, 3 kẹo: sum_val += nums[j], profit = max(profit, sum_val - table[j-i])
- Cập nhật table = [profit, table[0], table[1]]
- Người 1 thắng nếu table[0] > 0
Ví dụ minh họa
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