题目重点：同高度或同顶色才能叠，减少堆数保证游戏终止。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 输入stack=(height,topColor)，两堆高度相同或顶色相同可合并，高度相加，顶色由放在上面的堆决定。
- 训练采用正常胜负：无法移动者输、最后行动者胜。源主要要求实现游戏，胜负分析是明确训练扩展；若misère规则则边界相反。
解题路线
- 合法操作枚举两堆及两种上下方向。所有未来规则只看高度/顶色，排序stack multiset作为canonical state，不保留与规则无关的tile内部顺序。
- winning(state)=存在某合法后继为losing；无后继False。每次堆数−1，状态无环，memo复用不同操作到达的同状态。
- 如果要实际game API，额外校验当前轮次、选堆ID和游戏结束。memo solver用canonical状态，UI身份则仍需稳定ID映射，二者职责不同。
手动走一遍
两堆(1,红),(2,蓝)高度/顶色都不同，没有动作，当前输。两堆(1,红),(1,蓝)可合成一个，下一玩家无动作，当前赢。三堆高度1且同红：每步都可合，总两次动作，所以先手输。对混色不应只按初始堆数奇偶猜。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from functools import lru_cache
def winning(stacks):
state=tuple(sorted(stacks))
if any(height<=0 for height,color in state):raise ValueError("positive stack heights required")
@lru_cache(None)
def solve(state):
for i,(hi,ci) in enumerate(state):
for j in range(i+1,len(state)):
hj,cj=state[j]
if hi!=hj and ci!=cj:continue
rest=[s for k,s in enumerate(state) if k not in (i,j)]
for top in {ci,cj}:
next_state=tuple(sorted(rest+[(hi+hj,top)]))
if not solve(next_state):return True
return False
return solve(state)
复杂度
状态空间随堆数、总高度和颜色数快速增长；每state枚举O(s²)对及排序后继O(slogs)，memo空间按不同state数。有限12块场景也应实测，不承诺任意n多项式。
易错点与追问
容易失分的边界
- 同高度OR同色，不是同时满足两项。
- 只生成一种上下方向会漏掉顶色不同的后续可能性。
继续深挖
- 输出一条必胜首步及后续策略，需要memo额外保存什么？
- 如果只能合相邻堆，为什么排序multiset不再是有效状态压缩？
