题目重点：从合法抽牌修复到局部三数和策略，再对照已知牌序的全局最优搜索，解释为何不能保证每局满分。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练明确定义：移除三张后按牌堆顺序补至16张，牌堆耗尽后不补；没有合法三张即结束。花色仅区分实体，计分只看点数，不能重复使用同一张。
- 代码给出“未来牌序全可见”的offline精确基准；真实在线策略看不到牌堆，不能把offline选择当成可实现的公平策略。未知补牌与可见信息必须先问。
- 题目举例9+3+2不等于15，正确合法示例是9+4+2、5+5+5。36张总点数180，每组三张15意味着至多12组，每组得15，最高分180；上界不等于必可达。
解题路线
- 先修抽牌合法性：核验三个实体ID都在桌上、互不重复、点数和15，校验完整后才改变游戏状态。仅检查点数存在会错误允许桌上两张5抽出三张5。
- 局部baseline枚举桌面三组合，任选合法三张；16张仅560个组合。每次赚15不保证后续总分最大，不能把3SUM查找与策略优化混为同一问题。
- offline状态为(排序桌面点数多重集合,deckPosition)，枚举合法三张后补牌，递归最大化15+futureScore，memo去重。花色对规则无影响时等值三张合并动作；保留物理ID的oracle独立穷举核对该简化。
- 在线若牌堆隐藏，可用同信息条件下的启发式/有限滚动模拟估计后续价值；不得读取模拟器完整deck作为策略输入。已知剩余牌分布和完全未知是不同模型，抽样要与真实信息一致。
- 评估用同一组seed/deck对各策略配对比较，报告平均分、满分率、P10、耗时、置信区间与超时比例；调参deck和最终测试deck分离。100局的满分率有明显抽样不确定性，不能把一次结果当稳赢证明。
手动走一遍
合法桌面[5,5,5]抽三张得15；[5,5]不能虚构第三张。初始16张全为四张6/7/8/9，没有任何和15的三张，立刻0分，说明任何策略都无法保证每局180。程序在小牌堆上与保留唯一实体ID的全行动树核对500例。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from functools import lru_cache
from itertools import combinations
def optimal_offline_card_game(table, deck, table_capacity=16, target=15):
"""Return (max_score, initial triple of values or None).
Training model: all future deck order is KNOWN to the solver; draw replacements
in that order immediately after each triple removal until table capacity or
deck exhaustion. Faces/suits only identify physical copies; scoring depends
solely on rank. Each selected triple sums to target and earns 15 points.
Not an online hidden-deck strategy, not a polynomial-time large-instance claim.
"""
if table_capacity < 3 or len(table) > table_capacity:
raise ValueError('invalid table capacity')
if any(not isinstance(v, int) or not 1 <= v <= 9 for v in (*table, *deck)):
raise ValueError('card ranks must be integers from 1 through 9')
deck = tuple(deck)
@lru_cache(None)
def solve(current, position):
best_score = 0
best_triple = None
seen = set()
for selected in combinations(range(len(current)), 3):
triple = tuple(current[i] for i in selected)
if sum(triple) != target or triple in seen:
continue
seen.add(triple)
remaining = [v for i, v in enumerate(current) if i not in selected]
draw_count = min(table_capacity-len(remaining), len(deck)-position)
remaining.extend(deck[position:position+draw_count])
future, _ = solve(tuple(sorted(remaining)), position+draw_count)
score = 15 + future
if score > best_score:
best_score, best_triple = score, triple
return best_score, best_triple
return solve(tuple(sorted(table)), 0)
def remove_legal_triple(table, triple):
"""Copy table, verify physical multiplicities BEFORE removal; return remaining."""
if len(triple) != 3 or sum(triple) != 15:
raise ValueError('three cards summing to 15 required')
remaining = list(table)
for card in triple:
if card not in remaining:
raise ValueError('selected cards must be present with sufficient multiplicity')
remaining.remove(card)
return remaining
复杂度
每状态最多C(T,3)动作，T<=16；总时间O(S·C(T,3)·T)，S为可达桌面多重集/牌堆位置状态数，仍可能指数级。memo与路径栈O(S+totalCards)，完整36牌精确搜索没有多项式或运行时保证。合法三张验证复制桌面O(T)。
易错点与追问
容易失分的边界
- 让AI生成大段DP后只看测试绿灯，无法证明没有偷看未来、没有复用牌或改变补牌顺序。
- 把随机游戏“90%满分”写成算法保证，会忽略seed、样本量、规则与牌序分布。
- 0合法动作是正常终局，不应无限补牌或重抽把难局改成可解。
继续深挖
- 若要求总是满分，先给不可解初始桌面反例；若只在可解牌序里最优，仍需明确能否看到未来。
- 如何减少搜索？点数计数替代实体排列、合法动作去重、上界剪枝与缓存；上界可用剩余张数/3×15，注意未发牌在堵局时不一定可使用。
- 若花色加入约束，点数多重集不再充分，状态需保存花色并重做等价性证明。
