MIT 6.006 第15课讲义
MIT 6.006 第16课讲义
MIT 6.006 第17课讲义(多个类似floyd思想的动态规划)
MIT 6.006 第18课讲义(大概再讲一个背包问题)

问题描述

这是一个经典的双人零和博弈问题：

  • 有 nn 个硬币排成一行，价值为 v0,v1,…,vn−1v_0, v_1, \ldots, v_{n-1}
  • 两名玩家轮流取硬币，每次只能取最左边或最右边的硬币
  • "我"先手，目标是最大化自己取的硬币总价值
  • 这是一个零和游戏：我获得的价值 = 总价值 - 对手获得的价值

问题分析

关键洞察

由于是零和博弈，我的目标等价于最大化「我的价值 - 对手的价值」。在每一步中，我需要考虑对手会采取最优策略来最小化我的收益。

状态定义

定义子问题：

dp[i][j]=在硬币区间 [i,j] 上，当前玩家能获得的最大价值dp[i][j] = \text{在硬币区间 } [i,j] \text{ 上，当前玩家能获得的最大价值}

注意：这里的"当前玩家"可能是"我"或"对手"，取决于游戏进度。

动态规划解法

1. 递推关系

对于区间 [i,j][i, j]，当前玩家有两种选择：

  1. 取左边的硬币 viv_i

    • 获得价值 viv_i
    • 对手在区间 [i+1,j][i+1, j] 上采取最优策略
    • 净收益：vi−dp[i+1][j]v_i - dp[i+1][j]

  2. 取右边的硬币 vjv_j

    • 获得价值 vjv_j
    • 对手在区间 [i,j−1][i, j-1] 上采取最优策略
    • 净收益：vj−dp[i][j−1]v_j - dp[i][j-1]

因此递推式为：

dp[i][j]=max⁡(vi−dp[i+1][j],vj−dp[i][j−1])dp[i][j] = \max(v_i - dp[i+1][j], v_j - dp[i][j-1])

2. 基本情况

当区间只有一个硬币时：

dp[i][i]=vidp[i][i] = v_i

3. 最终答案

原问题的解需要稍作转换：

我的最大价值=总价值+dp[0][n−1]2\text{我的最大价值} = \frac{\text{总价值} + dp[0][n-1]}{2}

因为 dp[0][n−1]dp[0][n-1] 表示「先手玩家价值 - 后手玩家价值」。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def coin_game(coins):
    """
    交替取硬币游戏 - 零和博弈解法
    
    Args:
        coins: List[int] - 硬币价值列表
        
    Returns:
        tuple: (我的最大价值, 对手价值, 总价值)
    """
    n = len(coins)
    if n == 0:
        return 0, 0, 0
    
    # dp[i][j] = 在区间[i,j]上，当前玩家能获得的最大价值
    dp = [[0] * n for _ in range(n)]
    
    # 基本情况：单个硬币
    for i in range(n):
        dp[i][i] = coins[i]
    
    # 按区间长度递增计算
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # 当前玩家取左边或右边的最大值
            take_left = coins[i] - dp[i + 1][j]
            take_right = coins[j] - dp[i][j - 1]
            dp[i][j] = max(take_left, take_right)
    
    total_value = sum(coins)
    my_value = (total_value + dp[0][n - 1]) // 2
    opponent_value = total_value - my_value
    
    return my_value, opponent_value, total_value

def reconstruct_strategy(coins, dp):
    """
    重建最优策略路径
    """
    n = len(coins)
    i, j = 0, n - 1
    my_moves = []
    opponent_moves = []
    my_turn = True
    
    while i <= j:
        if my_turn:
            # 我的回合：选择收益更大的方向
            if coins[i] - dp[i + 1][j] >= coins[j] - dp[i][j - 1]:
                my_moves.append(f"取左边 v[{i}] = {coins[i]}")
                i += 1
            else:
                my_moves.append(f"取右边 v[{j}] = {coins[j]}")
                j -= 1
        else:
            # 对手的回合：对手也会选择收益更大的方向
            if coins[i] - dp[i + 1][j] >= coins[j] - dp[i][j - 1]:
                opponent_moves.append(f"取左边 v[{i}] = {coins[i]}")
                i += 1
            else:
                opponent_moves.append(f"取右边 v[{j}] = {coins[j]}")
                j -= 1
        my_turn = not my_turn
    
    return my_moves, opponent_moves