Mô phỏng thuật toán Trò lấy sỏi hai đầu (DP đoạn)

Stone Game (Interval DP) · Nhóm: Lý thuyết trò chơi

Trò lấy sỏi hai đầu: hai người luân phiên lấy một đống ở đầu trái hoặc đầu phải, mỗi người tối đa hoá tổng của mình trừ đi tổng đối thủ; giải bằng quy hoạch động trên đoạn.

Ý tưởng

dp[i][j] = chênh lệch điểm tốt nhất cho người tới lượt trên đoạn [i..j] = max(piles[i] − dp[i+1][j], piles[j] − dp[i][j−1]).

Điền theo độ dài đoạn tăng dần; cơ sở dp[i][i] = piles[i]; đáp số dp[0][n−1].

Vì sao đúng

Lấy một đầu rồi trừ đi chênh lệch tốt nhất mà đối thủ đạt được trên đoạn còn lại chuyển bài toán đối kháng thành đệ quy đơn nhân vật trên chênh lệch điểm; dp[0][n−1] > 0 nghĩa là người đi trước bảo đảm tổng lớn hơn.

Mã Python

def stone_game(piles):
    n = len(piles)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):                 # base case: single pile
        dp[i][i] = piles[i]
    for length in range(2, n + 1):     # interval length
        for i in range(n - length + 1):
            j = i + length - 1
            take_left  = piles[i] - dp[i + 1][j]
            take_right = piles[j] - dp[i][j - 1]
            dp[i][j] = max(take_left, take_right)
    return dp[0][n - 1]                # positive => first player wins

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.