题目重点：OA 题目给相邻同字符额外 sameTime、切一刀花 partitionTime；按公开规则各边独立，线性扫描即可，并用所有切法穷举验证。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版每个相邻相同字符对，若不在此处切段就额外花 sameTime；每切一刀固定花 partitionTime；不同边之间无相互作用，可切任意多刀。
- 空串或单字符没有相邻边，代价 0；两个时间均非负。若每段有固定启动成本、最多 K 段或压缩状态跨边影响，则不能用本算法。
解题路线
- 把 n−1 个字符间隙分别看作切或不切的二元决策。若相邻字符不同，不切额外代价 0，非负切割费下必不切。
- 若相邻相同，不切花 sameTime，切花 partitionTime；选择 min，两端边决策在公开规则下互不影响。
- 遍历每个相邻对累加局部最小值，时间 O(n)、额外 O(1)；无需区间 DP。
- 对长度≤8 的随机字符串枚举所有 2^(n−1) 种切法作独立参考，验证 10,000 组与题目示例。
手动走一遍
s='abbaa' 的相同相邻边是 bb 与 aa 两处。每处忍受成本 5 或切段成本 1，选两次切共 2；其他边不切成本 0。若 partitionTime=7、sameTime=5，则两处都不切，共 10。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Choose whether to cut at each adjacent-equal pair to minimize extra time."""
def min_extra_time(text: str, same_time: int, partition_time: int) -> int:
if same_time < 0 or partition_time < 0:
raise ValueError("times must be nonnegative")
return sum(min(same_time, partition_time) for left, right in zip(text, text[1:]) if left == right)
复杂度
n 个字符扫描 n−1 个间隙，O(n) 时间、O(1) 额外空间。题目所称区间 DP 在给出的独立边费用规则下不是必要的；若有全局段数限制，状态复杂度另算。
易错点与追问
容易失分的边界
- 无额外段约束却套 O(n²) 区间 DP，未识别相邻边独立性。
- 对不同字符间隙也付 sameTime。
- 无论切与不切都同时付费，双重计数。
- 忽略空串和单字符边界。
- 将题目描述提到的区间 DP 当成真实题面必需条件。
继续深挖
- 若最多允许 K 刀，如何按收益排序或做 DP？
- 若每段有固定头部费用，与每刀费用是否等价？
- 若相邻重复跨网络包才算罚时，而包长有上限，状态如何改变？
