动态规划进阶：博弈DP深度解析

1. 博弈DP概述

博弈DP是动态规划在博弈论问题中的应用，主要解决两个或多个玩家轮流做出最优决策的问题。这类问题通常涉及"零和博弈"，即一方的收益等于另一方的损失。

2. 博弈DP基本概念

2.1 博弈DP特点

• 轮流决策：玩家交替做出决策
• 最优策略：每个玩家都采取对自己最有利的策略
• 状态转移：当前状态由前一个状态和玩家决策决定
• 胜负判断：通常判断先手是否必胜

2.2 通用解题思路

3. 石子游戏系列

3.1 预测赢家 (LeetCode 486)

问题描述：玩家可以从数组两端取数字，预测先手是否能赢。

状态定义

dp[i][j]：在区间[i,j]内，先手能比后手多得的分数

状态转移

dp[i][j] = max(nums[i] – dp[i+1][j], nums[j] – dp[i][j-1])

Python实现

def PredictTheWinner(nums):
"""
预测赢家 – 区间DP
返回：先手是否能赢（得分>=0）
"""
n = len(nums)

# 方法1：二维DP
dp = [[0] * n for _ in range(n)]

# 初始化：单个数字时，先手获得该数字
for i in range(n):
dp[i][i] = nums[i]

# 按区间长度从小到大遍历
for length in range(2, n + 1):
for i in range(n – length + 1):
j = i + length – 1
# 先手可以选择i或j，然后变成后手
dp[i][j] = max(nums[i] – dp[i+1][j],
nums[j] – dp[i][j–1])

return dp[0][n–1] >= 0

#### 空间优化版本
def PredictTheWinner_optimized(nums):
"""
空间优化：使用一维数组
"""
n = len(nums)
dp = nums.copy() # 初始化长度为1的区间

for length in range(2, n + 1):
for i in range(n – length + 1):
j = i + length – 1
dp[i] = max(nums[i] – dp[i+1],
nums[j] – dp[i]) # 注意：这里的dp[i]会被覆盖

return dp[0] >= 0

#### 记忆化搜索
def PredictTheWinner_memo(nums):
from functools import lru_cache

@lru_cache(None)
def dfs(i, j):
"""返回在区间[i,j]内，先手能比后手多得的分数"""
if i == j:
return nums[i]

# 先手可以选择i或j
pick_left = nums[i] – dfs(i+1, j)
pick_right = nums[j] – dfs(i, j–1)

return max(pick_left, pick_right)

return dfs(0, len(nums)–1) >= 0

Java实现

public class PredictTheWinner {
// 二维DP解法
public boolean predictTheWinner(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][n];

// 初始化对角线
for (int i = 0; i < n; i++) {
dp[i][i] = nums[i];
}

// 按区间长度遍历
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n – len; i++) {
int j = i + len – 1;
dp[i][j] = Math.max(
nums[i] – dp[i+1][j],
nums[j] – dp[i][j–1]
);
}
}

return dp[0][n–1] >= 0;
}

// 空间优化版本
public boolean predictTheWinnerOptimized(int[] nums) {
int n = nums.length;
int[] dp = new int[n];

for (int i = 0; i < n; i++) {
dp[i] = nums[i];
}

for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n – len; i++) {
int j = i + len – 1;
dp[i] = Math.max(nums[i] – dp[i+1], nums[j] – dp[i]);
}
}

return dp[0] >= 0;
}
}

3.2 石子游戏 (LeetCode 877)

问题描述：石子堆成一行，玩家可以从两端取石子，判断先手是否能赢。

def stoneGame(piles):
"""
石子游戏 – 简化版
注意：本题中石子堆数为偶数，且石子总数为奇数
在这种条件下，先手总是能赢
"""
# 数学解法：先手总是能赢
return True

#### DP解法（通用）
def stoneGame_dp(piles):
"""
DP解法，适用于一般情况
"""
n = len(piles)
dp = [[0] * n for _ in range(n)]

# 初始化
for i in range(n):
dp[i][i] = piles[i]

# 状态转移
for length in range(2, n + 1):
for i in range(n – length + 1):
j = i + length – 1
# 当前玩家可以选择i或j
dp[i][j] = max(piles[i] – dp[i+1][j],
piles[j] – dp[i][j–1])

return dp[0][n–1] > 0

#### 带差值的版本
def stoneGame_with_diff(piles):
"""
返回先手能比后手多得的石子数
"""
n = len(piles)

# dp[i][j] = (先手得分, 后手得分)
dp = [[(0, 0)] * n for _ in range(n)]

# 初始化：只有一堆石子时
for i in range(n):
dp[i][i] = (piles[i], 0)

# 状态转移
for length in range(2, n + 1):
for i in range(n – length + 1):
j = i + length – 1

# 如果先手取左边
left_first = piles[i] + dp[i+1][j][1]
left_second = dp[i+1][j][0]

# 如果先手取右边
right_first = piles[j] + dp[i][j–1][1]
right_second = dp[i][j–1][0]

# 先手会选择对自己更有利的方案
if left_first – left_second > right_first – right_second:
dp[i][j] = (left_first, left_second)
else:
dp[i][j] = (right_first, right_second)

first_score, second_score = dp[0][n–1]
return first_score – second_score

3.3 石子游戏 II (LeetCode 1140)

问题描述：玩家可以取前X堆石子（1 ≤ X ≤ 2M），然后M变为max(M, X)。

def stoneGameII(piles):
"""
石子游戏 II – 带限制的取石子
"""
n = len(piles)

# 后缀和，用于快速计算区间和
suffix_sum = [0] * (n + 1)
for i in range(n–1, –1, –1):
suffix_sum[i] = suffix_sum[i+1] + piles[i]

# dp[i][m]: 从位置i开始，M=m时，当前玩家能获得的最大石子数
dp = [[0] * (n+1) for _ in range(n+1)]

# 从后往前计算
for i in range(n–1, –1, –1):
for m in range(1, n+1):
# 如果可以把剩下的全部取走
if i + 2 * m >= n:
dp[i][m] = suffix_sum[i]
else:
# 尝试所有可能的X
for x in range(1, 2*m + 1):
next_m = max(m, x)
# 当前玩家取x堆，然后轮到对手
current_take = suffix_sum[i] – suffix_sum[i+x]
opponent_take = dp[i+x][next_m]
dp[i][m] = max(dp[i][m], current_take + (suffix_sum[i+x] – opponent_take))

return dp[0][1]

#### 记忆化搜索版本
def stoneGameII_memo(piles):
from functools import lru_cache

n = len(piles)

# 后缀和
suffix_sum = [0] * (n + 1)
for i in range(n–1, –1, –1):
suffix_sum[i] = suffix_sum[i+1] + piles[i]

@lru_cache(None)
def dfs(i, m):
"""从位置i开始，M=m时，当前玩家能获得的最大石子数"""
if i >= n:
return 0

# 如果可以把剩下的全部取走
if i + 2 * m >= n:
return suffix_sum[i]

best = 0
for x in range(1, 2*m + 1):
next_m = max(m, x)
# 当前玩家取x堆
current_take = suffix_sum[i] – suffix_sum[i+x]
# 对手从i+x开始取
opponent_take = dfs(i+x, next_m)
# 当前玩家总获得 = 当前取走的 + (剩下的 – 对手能获得的)
total = current_take + (suffix_sum[i+x] – opponent_take)
best = max(best, total)

return best

return dfs(0, 1)

4. 硬币游戏系列

4.1 硬币游戏 (LeetCode 877变种)

问题描述：一排硬币，玩家从两端取硬币，求先手能获得的最大金额。

def coinGame(coins):
"""
硬币游戏 – 预测赢家的变种
"""
n = len(coins)

# 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

# 情况1：先手取coins[i]，后手在[i+1,j]中取
# 后手会最大化自己的收益，所以先手得到：
# coins[i] + min(dp[i+2][j], dp[i+1][j-1])
pick_left = coins[i] + min(
dp[i+2][j] if i+2 <= j else 0,
dp[i+1][j–1] if i+1 <= j–1 else 0
)

# 情况2：先手取coins[j]，后手在[i,j-1]中取
pick_right = coins[j] + min(
dp[i+1][j–1] if i+1 <= j–1 else 0,
dp[i][j–2] if i <= j–2 else 0
)

dp[i][j] = max(pick_left, pick_right)

# 计算总金额
total = sum(coins)
first_player = dp[0][n–1]

return first_player > total – first_player # 先手是否能赢

4.2 Nim游戏 (LeetCode 292)

问题描述：桌上有一堆石头，每次可以取1-3个，最后取光的人获胜。

def canWinNim(n):
"""
Nim游戏 – 简单的数学规律
如果石头数是4的倍数，先手必输；否则先手必胜
"""
return n % 4 != 0

#### DP解法（理解原理）
def canWinNim_dp(n):
"""
DP解法，展示博弈DP思想
"""
if n <= 3:
return True

# dp[i]: 有i个石头时，当前玩家是否能赢
dp = [False] * (n + 1)

# 初始化
dp[1] = dp[2] = dp[3] = True

for i in range(4, n + 1):
# 如果当前玩家取1、2或3个石头后，对方必输，则当前玩家能赢
dp[i] = not dp[i–1] or not dp[i–2] or not dp[i–3]

return dp[n]

#### 推广到可以取1-m个
def canWinNim_general(n, m):
"""
推广的Nim游戏：每次可以取1-m个
"""
if n <= m:
return True

# 如果n % (m+1) == 0，先手必输；否则先手必胜
return n % (m + 1) != 0

5. 卡片游戏

5.1 翻转游戏 (LeetCode 294)

问题描述：字符串中有"++“，可以翻转成”–"，无法操作的人输。

def canWin(s):
"""
翻转游戏 – 记忆化搜索
"""
from functools import lru_cache

@lru_cache(None)
def dfs(state):
"""当前字符串状态下，当前玩家是否能赢"""
# 尝试所有可能的移动
for i in range(len(state) – 1):
if state[i:i+2] == "++":
# 执行翻转
new_state = state[:i] + "–" + state[i+2:]
# 如果对手不能赢，则当前玩家能赢
if not dfs(new_state):
return True
return False

return dfs(s)

#### 优化的SG函数版本
def canWin_optimized(s):
"""
使用SG函数（Sprague-Grundy）优化
"""
from functools import lru_cache

@lru_cache(None)
def sg(length):
"""计算长度为length的连续'+'的SG值"""
if length <= 1:
return 0

# 所有可能的后续状态的SG值
moves = set()
for i in range(length – 1):
# 翻转i和i+1位置
left_len = i
right_len = length – i – 2
moves.add(sg(left_len) ^ sg(right_len))

# 计算mex（最小排除值）
mex = 0
while mex in moves:
mex += 1
return mex

# 分割字符串，计算每个连续'+'段
segments = []
count = 0
for ch in s:
if ch == '+':
count += 1
else:
if count > 0:
segments.append(count)
count = 0
if count > 0:
segments.append(count)

# 计算总的SG值（异或和）
total_sg = 0
for seg in segments:
total_sg ^= sg(seg)

return total_sg != 0 # SG值不为0表示先手必胜

6. 井字棋游戏

6.1 井字棋胜负判断

def tictactoe(moves):
"""
井字棋游戏 – 判断胜负
"""
n = 3
board = [[' ' for _ in range(n)] for _ in range(n)]

# 填充棋盘
for i, (r, c) in enumerate(moves):
player = 'A' if i % 2 == 0 else 'B'
board[r][c] = player

def check_win(player):
"""检查玩家是否获胜"""
# 检查行
for r in range(n):
if all(board[r][c] == player for c in range(n)):
return True

# 检查列
for c in range(n):
if all(board[r][c] == player for c in range(n)):
return True

# 检查对角线
if all(board[i][i] == player for i in range(n)):
return True
if all(board[i][n–1–i] == player for i in range(n)):
return True

return False

# 检查A和B是否获胜
if check_win('A'):
return "A"
if check_win('B'):
return "B"

# 判断是否平局或进行中
if len(moves) == n * n:
return "Draw"
else:
return "Pending"

#### 井字棋完美AI（极小化极大算法）
def tictactoe_ai(board):
"""
井字棋AI – 极小化极大算法
返回最佳移动位置
"""
def evaluate(board):
"""评估当前棋盘状态"""
# 检查行、列、对角线
lines = []
for i in range(3):
lines.append([board[i][0], board[i][1], board[i][2]]) # 行
lines.append([board[0][i], board[1][i], board[2][i]]) # 列

lines.append([board[0][0], board[1][1], board[2][2]]) # 主对角线
lines.append([board[0][2], board[1][1], board[2][0]]) # 副对角线

for line in lines:
if line.count('X') == 3:
return 10 # AI赢
if line.count('O') == 3:
return –10 # 玩家赢

return 0 # 平局或未结束

def is_moves_left(board):
"""检查是否还有空位"""
for row in board:
if ' ' in row:
return True
return False

def minimax(board, depth, is_max):
"""极小化极大算法"""
score = evaluate(board)

# 如果游戏结束，返回分数
if score == 10 or score == –10:
return score – depth # 深度越小越好

# 如果没有空位，平局
if not is_moves_left(board):
return 0

if is_max:
# AI的回合，最大化分数
best = –float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == ' ':
board[i][j] = 'X'
best = max(best, minimax(board, depth+1, False))
board[i][j] = ' ' # 回溯
return best
else:
# 玩家的回合，最小化分数
best = float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == ' ':
board[i][j] = 'O'
best = min(best, minimax(board, depth+1, True))
board[i][j] = ' ' # 回溯
return best

# 寻找最佳移动
best_val = –float('inf')
best_move = (–1, –1)

for i in range(3):
for j in range(3):
if board[i][j] == ' ':
board[i][j] = 'X'
move_val = minimax(board, 0, False)
board[i][j] = ' ' # 回溯

if move_val > best_val:
best_move = (i, j)
best_val = move_val

return best_move

7. 博弈DP的优化技巧

7.1 记忆化搜索

对于复杂的博弈树，记忆化搜索比迭代DP更直观。

def game_dp_memo(state):
from functools import lru_cache

@lru_cache(None)
def can_win(current_state, is_first_player):
"""当前状态下，当前玩家是否能赢"""
# 终止条件
if is_terminal(current_state):
return not is_first_player # 根据游戏规则调整

# 尝试所有可能的移动
for next_state in get_possible_moves(current_state):
# 如果对手不能赢，则当前玩家能赢
if not can_win(next_state, not is_first_player):
return True

return False

return can_win(state, True)

7.2 SG函数（Sprague-Grundy）

对于组合博弈，SG函数是强大的工具。

def calculate_sg(state):
"""
计算状态的SG值
SG值不为0表示必胜，为0表示必败
"""
from functools import lru_cache

@lru_cache(None)
def sg(current_state):
"""计算当前状态的SG值"""
# 获取所有可能的后继状态
next_states = get_next_states(current_state)

if not next_states: # 没有后继状态，必败
return 0

# 计算所有后继状态的SG值
sg_values = set()
for next_state in next_states:
sg_values.add(sg(next_state))

# 计算mex（最小排除值）
mex = 0
while mex in sg_values:
mex += 1
return mex

return sg(state)

7.3 对称性优化

利用游戏的对称性减少状态空间。

def symmetric_game(state):
"""
利用对称性优化博弈DP
"""
def normalize(state):
"""标准化状态，将对称状态映射为同一表示"""
# 例如，在棋盘游戏中，旋转和翻转可能产生相同状态
# 返回标准化后的状态
return min(
state,
rotate(state),
rotate(rotate(state)),
rotate(rotate(rotate(state))),
flip(state),
flip(rotate(state)),
# … 其他对称变换
)

from functools import lru_cache

@lru_cache(None)
def dfs(normalized_state):
# … 博弈逻辑

return dfs(normalize(state))

8. 复杂博弈问题

8.1 除数博弈 (LeetCode 1025)

问题描述：玩家轮流选择0 < x < N且N % x == 0，然后N = N – x，无法操作的人输。

def divisorGame(N):
"""
除数博弈 – 数学规律
N为偶数时先手必胜，奇数时先手必败
"""
return N % 2 == 0

#### DP解法
def divisorGame_dp(N):
"""
DP解法，展示博弈DP思想
"""
# dp[i]: 数字为i时，当前玩家是否能赢
dp = [False] * (N + 1)

# 初始化
dp[1] = False # 数字1时，无法操作，当前玩家输

for i in range(2, N + 1):
# 尝试所有可能的除数
for x in range(1, i):
if i % x == 0:
# 如果存在一个除数使得对手必败，则当前玩家能赢
if not dp[i – x]:
dp[i] = True
break

return dp[N]

8.2 猫和老鼠 (LeetCode 913)

问题描述：猫和老鼠在无向图上追逐，判断游戏结果。

def catMouseGame(graph):
"""
猫和老鼠 – 复杂博弈
返回：1-老鼠赢，2-猫赢，0-平局
"""
from functools import lru_cache

N = len(graph)

DRAW, MOUSE_WIN, CAT_WIN = 0, 1, 2

@lru_cache(None)
def dfs(mouse, cat, turn):
"""返回当前状态的结果"""
# 老鼠到达0洞，老鼠赢
if mouse == 0:
return MOUSE_WIN

# 猫抓到老鼠，猫赢
if mouse == cat:
return CAT_WIN

# 超过2N步，平局（防止无限循环）
if turn >= 2 * N:
return DRAW

# 当前玩家尝试所有可能的移动
if turn % 2 == 0: # 老鼠的回合
best_result = CAT_WIN # 老鼠希望最小化这个值（老鼠赢=1最小）
for next_mouse in graph[mouse]:
result = dfs(next_mouse, cat, turn + 1)
if result == MOUSE_WIN: # 老鼠找到必胜策略
return MOUSE_WIN
if result == DRAW:
best_result = DRAW
return best_result
else: # 猫的回合
best_result = MOUSE_WIN # 猫希望最大化这个值（猫赢=2最大）
for next_cat in graph[cat]:
if next_cat == 0: # 猫不能进0洞
continue
result = dfs(mouse, next_cat, turn + 1)
if result == CAT_WIN: # 猫找到必胜策略
return CAT_WIN
if result == DRAW:
best_result = DRAW
return best_result

return dfs(1, 2, 0)

9. 博弈DP解题模板

9.1 通用解题步骤

9.2 常见博弈类型

9.3 复杂度分析

9.4 调试技巧

def print_game_tree(state, depth=0, max_depth=3):
if depth > max_depth:
return

indent = " " * depth
print(f"{indent}State: {state}, Can win: {can_win(state)}")

if not is_terminal(state):
for next_state in get_moves(state):
print_game_tree(next_state, depth+1, max_depth)

def test_small_cases():
test_cases = [
([1], True), # 只有1个石子，先手赢
([1, 2], True), # 先手取2
([1, 5, 2], False), # 先手必输
]

for nums, expected in test_cases:
result = PredictTheWinner(nums)
assert result == expected, f"Failed for {nums}: {result} != {expected}"

def visualize_dp(dp):
n = len(dp)
print("DP Table:")
for i in range(n):
for j in range(n):
print(f"{dp[i][j]:3d}", end=" ")
print()

10. 面试准备建议

10.1 必备知识点

10.2 解题策略

10.3 沟通表达

11. 练习题目推荐

11.1 基础练习

11.2 进阶练习

11.3 挑战练习

12. 总结

博弈DP是动态规划中非常有趣且实用的一类问题，它结合了算法设计和游戏理论。掌握博弈DP需要：

核心要点：

学习建议：

博弈DP不仅在算法面试中常见，在游戏AI、自动推理等领域也有广泛应用。通过系统学习和大量练习，可以掌握这一重要技能。