每日练习与编程练习

我会把任务建模为单调在线决策：状态为已消费源帧 i、已提交目标 token j，动作为 READ 或 WRITE。训练阶段先用离线 teacher 构造一条低风险、低延迟的 oracle 轨迹。定义 WRITE 代价为 C_write(i,j)=L[i][j]+λ·delay(i,j)+γ·early_risk(i,j)，其中 delay 可用 DAL/AL 的近似，例如 max(0, i - j·N/M - δ)，early_risk 可由前缀置信度、强制对齐边界或熵惩罚给出；READ 代价可设为 μικ小等待惩罚或接近延迟上限时的增大惩罚。DP 为 dp[i][j] 表示读到 i、写出 j 个 token 的最小代价：READ 转移 dp[i+1][j] = min(dp[i+1][j], dp[i][j] + C_read(i,j))，WRITE 转移 dp[i][j+1] = min(dp[i][j+1], dp[i][j] + C_write(i,j+1))，边界 dp[0][0]=0，终点 dp[N][M]，回溯得到 READ/WRITE 标签。朴素复杂度 O(NM)，显存 O(NM) 或滚动数组 O(M)；工程上会用离线对齐边界 b_j 把 i 限制在 [b_j-w, b_j+w] 或 wait-k 邻域，降到 O(Mw)，否则长音频不可承受。

训练时用多任务损失：轨迹策略头做动作交叉熵，翻译头继续做 teacher-forcing NLL，再加延迟正则和稳定性正则。为了缓解离线 oracle 与在线分布不一致，我会做 scheduled sampling / prefix dropout，让模型见到不完整前缀和自身历史；对不同 λ 训练或蒸馏出多档 latency policy，线上按业务档位切换。

推理时每个流维护状态 (i,j)、encoder cache、decoder KV cache、一个小 beam 和已提交前缀。每来一块音频先更新编码器，然后计算下一 token 分布、动作概率、熵、top1-top2 margin、当前延迟余量。如果 WRITE 置信度足够且不会明显早译，提交 token；如果置信度低且延迟余量充足则 READ；如果接近 800ms 预算则强制 WRITE 或降级到更激进策略。Beam 只允许在未提交窗口内竞争，已提交 token 不改；设置最多 R 个 token 的 tentative rollback 窗口，只有连续 K 个 chunk 保持一致或置信度超过阈值才交给 TTS/vocoder。语音侧用短缓存、overlap-add/cross-fade 避免回滚导致爆音。

复杂度上，单流在线每步主要是一次增量 encoder 和 B 条 beam 的下一 token 计算，约 O(B·V_top) 或用 top-k/采样近似，cache 内存为 O(B·T_dec·d + T_enc·d)。服务端调度会把多个流按 chunk 时间和模型形状做 micro-batch，同时用 earliest-deadline-first 优先处理接近延迟违约的流；对长静音用 VAD 跳过，对过载场景降低 beam、缩短回滚窗口或切更小模型。关键边界包括：长距离语序重排会导致早译错误，需允许等待或输出占位；静音、噪声、口吃会污染轨迹，要做 VAD 和置信度门控；EOS 不能过早提交；源目标长度比例异常时 delay 函数要归一化；网络抖动下要把 chunk 到达时间而非帧编号纳入延迟统计。

参考解法：回溯 + 预处理回文表

核心思路： 1. 先用动态规划预处理 `pal[i][j]`，表示子串 `s[i..j]` 是否为回文。 2. 再从左到右做回溯枚举： - 每次尝试切出一个前缀子串 `s[start..end]` - 只有当它是回文时，才继续递归 3. 当 `start == n` 时，说明已经切完整个字符串，收集当前方案。

这样做的好处是：判断任意子串是否回文的代价从 O(n) 降到 O(1)，避免在回溯中重复检查。

python
from typing import List

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        # pal[i][j] = True 表示 s[i:j+1] 是回文串
        pal = [[False] * n for _ in range(n)]

        # 预处理回文表
        # 按子串长度从小到大填写
        for i in range(n - 1, -1, -1):
            pal[i][i] = True
            for j in range(i + 1, n):
                if s[i] == s[j] and (j - i == 1 or pal[i + 1][j - 1]):
                    pal[i][j] = True

        res = []
        path = []

        def dfs(start: int) -> None:
            if start == n:
                res.append(path[:])
                return

            for end in range(start, n):
                if pal[start][end]:
                    path.append(s[start:end + 1])
                    dfs(end + 1)
                    path.pop()

        dfs(0)
        return res
解练习分析：

1. 关键思想
- 这练习本质是“枚举所有合法切分方案”。
- 因为要求每一段都是回文，所以每次切分前必须知道某段是否回文。
- 如果直接在回溯里反复判断，会有大量重复计算。
- 所以先用 DP 预处理所有区间回文性，再回溯枚举答案，是最适合现场的主解法。

2. 为什么 `pal[i][j]` 可以这样转移
- 若 `s[i] == s[j]`，并且中间部分 `s[i+1..j-1]` 也是回文，那么 `s[i..j]` 就是回文。
- 边界情况：
  - 长度 1：天然是回文
  - 长度 2：只要两端相等就是回文

3. 复杂度
- 预处理回文表：O(n^2)
- 回溯枚举：输出敏感，最坏情况下方案数非常多，整体复杂度取决于答案规模
- 空间复杂度：
  - 回文表 O(n^2)
  - 递归栈和路径 O(n)

4. 易错点
- 忘记处理长度为 1 和 2 的回文边界
- 回溯时没有 `path.pop()`，导致状态污染
- 切片下标写错，`s[start:end]` 和 `s[start:end+1]` 的区别
- 只做回溯不做预处理，导致重复判断回文超时

5. 出练习者可能追问
- 能否不用 O(n^2) 的表，改成边回溯边判断？可以，但会重复检查，效率更差。
- 能否进一步优化空间？可以考虑按需记忆化回文判断，但本练习 n 很小，O(n^2) 表最清晰稳定。
- 如何证明不会漏解或重解？回溯按“下一段起点”单调推进，每个切分方案唯一对应一条搜索路径，因此不会重复。
- 如果要求输出字典序，怎么改？可以控制遍历顺序，或在最终结果上排序，但一般不建议在搜索中额外复杂化。