题目重点：IC15 onsite 的 pin min + exact screen size 变体；明确 Pin 类型是否可重复使用，给出一维 DP、无解边界与 BFS 对照。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版每种高度可无限次使用，且高度都是正整数、屏幕高度为非负整数；如果每类只能用一次，需改成 0/1 DP。
- 恰好等于 screen 才成功，无法填满返回 -1；screen=0 返回 0。
解题路线
- 令 dp[x] 表示恰好填满高度 x 的最少 Pin 数，初始化 dp[0]=0，其他状态为不可达。
- 从小到大枚举 x，尝试每个 h≤x，若 dp[x−h] 可达则用一枚 h 更新 dp[x]。因 Pin 可重复，用升序 x 能复用已求出的状态。
- 重复高度先去重不会改变答案；若需要输出具体选了哪些 Pin，在更新时记录上一个高度及所选 h。
- 独立用从 0 出发的 BFS 搜索高度状态；BFS 的层数就是最少枚数，在随机小屏幕上与 DP 对照。
手动走一遍
heights=[3,5]、screen=11，可以 3+3+5 共 3 枚；screen=7 无法恰好拼出，返回 -1；screen=0 不选 Pin，返回 0。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Unbounded pin heights: minimum count for exact screen height."""
def minimum_pins_exact_screen(heights: list[int], screen: int) -> int:
if screen < 0 or any(height <= 0 for height in heights):
raise ValueError("screen must be nonnegative and heights positive")
possible = sorted(set(heights))
unknown = screen + 1
best = [unknown] * (screen + 1)
best[0] = 0
for filled in range(1, screen + 1):
for height in possible:
if height > filled:
break
best[filled] = min(best[filled], best[filled - height] + 1)
return -1 if best[screen] == unknown else best[screen]
复杂度
设屏幕高度 S、不同类型 H，一维 DP 时间 O(SH)、空间 O(S)；若屏幕尺寸很大，逐高度枚举不适合，需要进一步询问数值上界或数论结构。
易错点与追问
容易失分的边界
- 把不超过 screen 的最大已填高度当作 exact 答案。
- 题目未说明可重复使用，就把 unbounded 版本声称为唯一原题。
- 不可达 dp 值参与更新导致假答案。
- 允许高度 0 或负数而不校验，破坏转移。
继续深挖
- 每种类型只有有限库存时，如何改状态？
- 目标从 min 改为 max 时，是否可能无限次选 Pin？
- 屏幕高度达十亿但类型很少时，如何避免 O(SH)？
