Cho mảng stones[i] giá trị viên đá i từ trái sang. Amal và Bimal chơi luân phiên, Amal đi trước. Mỗi lượt lấy đá trái hoặc phải, được điểm = tổng giá trị đá còn lại. Bimal muốn tối thiểu hóa chênh lệch điểm, Amal muốn tối đa hóa. Tìm chênh lệch điểm khi cả hai chơi tối ưu.
Ví dụ: stones = [6,4,2,5,3], đầu ra = 8 (kết quả mô phỏng chi tiết trong bài).
Giải pháp
Dynamic Programming trên đoạn (interval DP):
- n := len(stones), dp := mảng n phần tử 0
- Với i từ n-1 xuống 0:
- v := stones[i], run_sum := 0
- Với j từ i+1 đến n-1:
- new_run := run_sum + stones[j]
- dp[j] := max(new_run - dp[j], run_sum + v - dp[j-1])
- run_sum := new_run
- Trả về dp[n-1]
Ví dụ minh họa
Xem triển khai sau để hiểu rõ hơn:
def solve(stones):
n = len(stones)
dp = [0] * n
for i in range(n - 1, -1, -1):
v = stones[i]
run_sum = 0
for j in range(i + 1, n):
new_run = run_sum + stones[j]
dp[j] = max(new_run - dp[j], run_sum + v - dp[j - 1])
run_sum = new_run
return dp[n - 1]
stones = [6,4,2,5,3]
print(solve(stones))
Đầu vào
[6,4,2,5,3]
Đầu ra
8