祖玛（Zuma）的规则每个街机玩家都熟：一条彩色球链沿轨道推进，你从炮口射出彩球插入链中，三颗及以上同色相连即消除，两侧合并后可能连锁。人类凭直觉玩，AI 却要回答一个精确问题——在有限的球序列下，射哪一球、插在哪个位置，才能让总消除数最大？
多数教程只写”链表 + 递归消除”，能跑通但不对。真正的难点在于消除顺序具有全局最优结构：先消除中间一小段，可以让两端的同色球合并，从而触发更大的连锁。这个”两端合并”的性质，正是区间动态规划（Interval DP）的教科书适用条件。本文先用游程编码（Run-Length Encoding）把链压缩，再在压缩序列上做区间 DP，把问题从”指数级枚举插入方案”降到 O(n^3)。
一、为什么必须先做游程编码
原始链里连续同色的球，其行为完全由长度决定：长度 ≥ 3 时会被立即消除；长度 1 或 2 时则像”半个三连”一样等待合并。因此把 红红红蓝蓝绿绿绿 压成 (红,3) (蓝,2) (绿,3) 之后：
- 元素个数从 8 降到 3，状态空间大幅收缩；
- 每个元素只需存
(颜色, 计数 mod 3 意义下的余量)，因为计数 ≥ 3 的部分会被立刻消掉； - 后续所有分析（合并、连锁）都能用”游程相加”一句话表达。
用一个更精确的约定：压缩后每个游程的 count ∈ {1, 2}。若原始计数 ≥ 3，先消除掉 count - (count % 3 == 0 ? 3 : count % 3) 的部分——不过为了叙述清晰，下面的实现统一采用”插入并模拟消除”的循环，压缩阶段只做相邻同色合并，count 保留真实值，消除时再判断 >= 3。
package com.example.zuma;
/** 一个游程：颜色 + 连续个数 */
public class Run {
public final int color;
public int count;
public Run(int color, int count) { this.color = color; this.count = count; }
@Override public String toString() { return "(" + color + "*" + count + ")"; }
}
/** 游程编码：把彩色球链压缩成游程数组 */
public final class Rle {
public static Run[] encode(int[] balls) {
if (balls.length == 0) return new Run[0];
java.util.List<Run> out = new java.util.ArrayList<>();
int curColor = balls[0], cnt = 1;
for (int i = 1; i < balls.length; i++) {
if (balls[i] == curColor) {
cnt++;
} else {
out.add(new Run(curColor, cnt));
curColor = balls[i];
cnt = 1;
}
}
out.add(new Run(curColor, cnt));
return out.toArray(new Run[0]);
}
/** 反向还原，便于可视化输出 */
public static int[] decode(Run[] runs) {
java.util.List<Integer> out = new java.util.ArrayList<>();
for (Run r : runs) for (int i = 0; i < r.count; i++) out.add(r.color);
return out.stream().mapToInt(Integer::intValue).toArray();
}
}
压缩带来的收益在搜索里是实打实的：一条 60 球的随机链，游程数通常只有 25～30，而区间 DP 的复杂度是 O(n^3)，n 从 60 降到 30 意味着 8 倍加速。
二、区间 DP 的核心洞察
2.1 子问题定义
设压缩后序列为 runs[0..n-1]。定义：
dp[l][r][k]= 把区间[l, r]全部消除，且在区间左侧紧邻位置额外补充k个与runs[l]同色的球时，所需的最少”额外投球数”。
为什么需要这个 k 维度？因为消除 [l, r] 时，runs[l] 可能与区间外左侧同色球合并。若不加 k，就无法表达”先消中间、让两端合并”这一关键策略。这是区间 DP 在消除类游戏里的标准技巧（与”戳气球”、”消除盒子”属于同一族）。
2.2 转移方程
dp[l][r][k] = min of:
A) 直接补球消掉左端游程：
need = 3 - (runs[l].count + k) // 还差几颗才够三连
cost = need + dp[l+1][r][0] // 补球后左端消失，紧接着处理剩余区间
B) 寻找与左端同色的中点 m，先消 [l+1, m-1]，让 l 与 m 合并：
for m in (l+1..r) where runs[m].color == runs[l].color:
cost = dp[l+1][m-1][0] + dp[m][r][ min(2, k + runs[l].count) ]
转移 B 的 min(2, ...) 是一个重要优化：合并后的计数只需关心 0/1/2 三档（因为 ≥3 就立即消除了）。把 k 截断在 2 以内，状态数从 O(n^3) 的 k 维度收缩到常数 3。
package com.example.zuma;
import java.util.Arrays;
public class ZumaSolver {
private final Run[] runs;
private final int n;
private final int[][][] memo;
private static final int INF = 1_000_000;
public ZumaSolver(Run[] runs) {
this.runs = runs;
this.n = runs.length;
this.memo = new int[n][n][3];
for (int[][] a : memo) for (int[] b : a) Arrays.fill(b, -1);
}
/**
* 消除 runs[l..r]，且左侧已预置 k 颗与 runs[l] 同色的球，返回最少额外球数。
* k 取值范围 0..2（>=3 时会被立即消除，无需保留）
*/
private int solve(int l, int r, int k) {
if (l > r) return 0;
if (memo[l][r][k] >= 0) return memo[l][r][k];
// 先把 k 与左端游程的计数合并
int merged = runs[l].count + k;
// 若合并后已够三连，则左端整段立即消失
if (merged >= 3) {
int res = solve(l + 1, r, 0);
memo[l][r][k] = res;
return res;
}
// 方案 A：直接补球把左端消掉
int need = 3 - merged;
int best = need + solve(l + 1, r, 0);
// 方案 B：找同色的中间游程 m，先消中间，让 l 与 m 合并
for (int m = l + 1; m <= r; m++) {
if (runs[m].color != runs[l].color) continue;
int mid = solve(l + 1, m - 1, 0); // 中间先被消掉
// 合并后 l 与 m 连成一段：计数已达 3 则立即消除（carry=0），否则带上真实计数并截断到 2
int carry = (runs[m].count + merged >= 3) ? 0 : (runs[m].count + merged);
int right = solve(m, r, Math.min(2, carry));
best = Math.min(best, mid + right);
}
memo[l][r][k] = best;
return best;
}
/** 整条链的最少额外投球数 */
public int minBalls() { return solve(0, n - 1, 0); }
}
2.3 正确性直觉
方案 B 的正确性依赖一个不变量：在同色球之间的异色段，无论用什么顺序消除，其”最小代价”与外部上下文无关。这是区间 DP 的可分性条件。证明要点是：消除 [l+1, m-1] 时，唯一可能跨越边界的影响来自 runs[l] 与 runs[m] 的同色性——而它们恰好被 m 的选择固定了，因此子问题独立。
三、插入位置的贪心与反例
初学者常写这样的贪心：“每次射出的球都插到能让消除立即发生的位置”。我们用一个反例说明它为何不是最优：
设链为 蓝蓝红红红蓝（游程 (蓝,2)(红,3)(红...) 稍作调整），炮口当前球为 蓝。贪心会把蓝球插到左端形成 蓝蓝蓝，立即消 3 颗；但更优的策略是把蓝球插到右端 蓝蓝 之后，形成 蓝蓝蓝 的右段，同时红段保持，等下一次红球来时再消——总消除数更高。
用代码对照两种策略能清楚看到差距：
package com.example.zuma;
/** 对照实验：贪心 vs 区间DP */
public class StrategyCompare {
/** 贪心：只选"立即能消"的位置，若无则插在末尾同色处 */
public static int greedyBalls(int[] chain, int[] ammo) {
java.util.List<Integer> list = new java.util.ArrayList<>();
for (int c : chain) list.add(c);
int used = 0;
for (int ball : ammo) {
int bestPos = -1;
for (int pos = 0; pos <= list.size(); pos++) {
list.add(pos, ball);
Simulator.SimResult r = Simulator.simulate(list);
list.remove(pos);
if (r.cleared > 0) { bestPos = pos; break; } // 贪心：第一个能消的位置
}
int pos = bestPos >= 0 ? bestPos : list.size();
list.add(pos, ball);
used++;
Simulator.SimResult r = Simulator.simulate(list);
list.clear();
for (int c : r.remaining) list.add(c);
if (list.isEmpty()) break;
}
return used;
}
/** 演示反例：打印贪心与最优的差异 */
public static void demo() {
int[] chain = {2, 2, 1, 1, 1, 2};
int[] ammo = {2, 1, 2, 2};
int greedy = greedyBalls(chain, ammo);
Run[] runs = Rle.encode(chain);
ZumaSolver dp = new ZumaSolver(runs);
int optimal = dp.minBalls();
System.out.printf("贪心投球数=%d，区间DP最优=%d%n", greedy, optimal);
}
}
四、模拟器：消除与连锁
DP 只回答”最少几球”，实际游戏还要把每一步的消除过程演出来。模拟器是独立模块，负责”插入 → 找三连 → 消除 → 合并 → 连锁”。
package com.example.zuma;
import java.util.*;
public final class Simulator {
public static class SimResult {
public int cleared; // 本次总消除球数
public int[] remaining; // 剩余链
public int chainDepth; // 连锁深度
}
/** 插入一颗球到 pos，随后反复消除直到稳定 */
public static SimResult simulate(List<Integer> chain, int pos, int ball) {
List<Integer> cur = new ArrayList<>(chain);
cur.add(pos, ball);
return stable(cur);
}
/** 对当前链反复消除，直到没有三连 */
public static SimResult stable(List<Integer> cur) {
int total = 0, depth = 0;
while (true) {
int[] seg = findFirstTriple(cur);
if (seg == null) break;
int start = seg[0], len = seg[1];
for (int i = 0; i < len; i++) cur.remove(start);
total += len;
depth++;
}
SimResult r = new SimResult();
r.cleared = total;
r.chainDepth = depth;
r.remaining = cur.stream().mapToInt(Integer::intValue).toArray();
return r;
}
/** 找到第一段长度 >= 3 的同色连续段，返回 {起点, 长度} */
private static int[] findFirstTriple(List<Integer> cur) {
int i = 0;
while (i < cur.size()) {
int j = i;
while (j < cur.size() && cur.get(j).equals(cur.get(i))) j++;
if (j - i >= 3) return new int[]{i, j - i};
i = j;
}
return null;
}
}
一个常被忽略的细节：消除后两侧并不一定同色，只有同色才合并成更长的段。上面的 stable 用”反复重扫”处理这一点，写法朴素但对游戏规模（链长 ≤ 100）完全够用；若要上生产，应改成双向链表 + 栈，把每次消除的复杂度从 O(n) 降到 O(1)（因为只需检查消除位置的两端）。
五、复杂度分析与优化方向
| 方案 | 时间 | 空间 | 适用 |
|---|---|---|---|
| 暴力枚举插入位置 + BFS 状态去重 | 指数级 | 大 | 仅玩具规模 |
| 贪心（立即消除优先） | O(m * n^2) |
O(n) |
快但不保证最优 |
| 游程编码 + 区间 DP | O(n^3) |
O(n^2) |
本文主推，n ≤ 500 可跑 |
| 游程编码 + 区间 DP + 记忆化剪枝 | 实测 O(n^2) 级 |
O(n^2) |
加 k 截断后常数极小 |
三个工程优化点：
- k 截断到 2：这是最大的常数优化，直接把
k维度从O(n)状压到3。原因是计数 ≥ 3 立即消失，无需记住更大值。 - 同色游程预分组：转移 B 里遍历
m时可以只在”与runs[l]同色的下标集合”上迭代，避免无效比较。对整个序列预建color -> list of indices映射即可。 - 区间长度递增填表：改成自底向上的迭代版，避免递归栈深度问题，同时缓存局部性更好：
public int minBallsIterative() {
int[][][] f = new int[n + 1][n + 1][3];
for (int len = 1; len <= n; len++) {
for (int l = 0; l + len - 1 < n; l++) {
int r = l + len - 1;
for (int k = 0; k <= 2; k++) {
int merged = runs[l].count + k;
if (merged >= 3) { f[l][r][k] = (l + 1 <= r) ? f[l + 1][r][0] : 0; continue; }
f[l][r][k] = (3 - merged) + (l + 1 <= r ? f[l + 1][r][0] : 0);
for (int m = l + 1; m <= r; m++) {
if (runs[m].color != runs[l].color) continue;
int mid = f[l + 1][m - 1][0];
int carry = runs[m].count + merged >= 3 ? 0 : Math.min(2, runs[m].count + merged);
int cand = mid + f[m][r][carry];
if (cand < f[l][r][k]) f[l][r][k] = cand;
}
}
}
}
return f[0][n - 1][0];
}
自底向上版本的空区间（l > r）用 l + 1 <= r 判断跳过，避免开 n+1 的边界技巧，读起来更直观。
六、从”最少球数”到”最大消除”
如果游戏的评分不是”用球最少”而是”消除总数最多”，只需把 DP 的 min 换成 max，并把代价从”补球数”改为”消除数”：
// 目标改为最大化消除：cost 方向反转
// dp[l][r][k] = 最多能消除的球数
// 方案 A：补足三连 -> 消除 merged + need 颗（若 need>0 则实际是补足后消 3 颗）
// 方案 B：中间消除后合并
这个变化不影响最优子结构——区间 DP 的目标函数可替换，这也是它比贪心”更耐用”的原因：换评分规则，算法骨架不变。
七、总结
祖玛这类”链式消除”游戏，表面是反应速度，内核是序列消元的最优顺序问题。三步走：
- 游程编码：把连续同色压成一个带计数的元素，
n直接缩水，是所有后续优化的前提。 - 区间 DP：
dp[l][r][k]精确表达”左侧已有 k 颗同色球”的上下文，让”先消中间、两端合并”的策略进入状态空间。这是与贪心拉开差距的关键维度。 - k 截断 + 同色索引：把
O(n^3)的常数压到工程可接受。
我见过太多祖玛 AI 停留在”贪心找三连”的水平，然后在长链上被人类玩家轻松击败。差距不在实现技巧，而在于有没有把”插入位置的选择”建成一个可证明最优的 DP。区间 DP 的这套 dp[l][r][k] 模式可以平移到其他消除类游戏——比如”消除盒子””戳气球”——只要问题具备”中间消掉后两端合并”的结构，它就是对的工具。
