动态规划不是不能并行——是你还没找到它的「并行基因」
去年我在做语音端点检测（VAD）模块时，遇到一个典型的'教科书级尴尬'：串行版 HMM 前向 DP 在 ARM Cortex-A76 上跑一帧 MFCC 要 180ms，而实时系统要求端到端延迟 ≤30ms。
我第一反应是'换 GPU'，结果把 kernel 搬上 Mali-G78 后，性能反而更差——因为没处理好 dp[t][s] 对上一时刻整行状态的依赖，大量线程在等同一个内存地址，L1 cache miss 率飙到 65%。
那一刻我才真正意识到：动态规划的并行化，从来不是把 for 循环套个 #pragma omp parallel 就完事；它是对问题数学结构的一次逆向工程——你要亲手把它拆开，看清哪些依赖是刚性的、哪些是柔性的、哪些其实可以'假装没看见'。
下面这整篇文章，就是我过去两年在生物信息、语音识别、嵌入式路径规划三个领域反复验证过的 DP 并行化心法。它不讲定义，只讲你怎么动手；不画大饼，只告诉你 在哪条路上容易翻车、哪个参数调错会让加速比变成 0.8x、为什么你的 CUDA kernel 永远只跑满 30% 的 SM。
先问自己一个问题：你的 DP，真的需要全量同步吗？
很多工程师一看到'DP 必须按序计算'，就默认得用全局屏障（barrier）或原子操作来保序。但现实是：绝大多数经典 DP 问题的依赖图，远没有教科书里画得那么密不透风。
以编辑距离为例，状态转移方程：
dp[i][j] = min(
dp[i-1][j] + 1, // 依赖正上方
dp[i][j-1] + 1, // 依赖正左方
dp[i-1][j-1] + δ // 依赖左上方
);
表面看，每个格子都要等三个邻居——但如果你把坐标 (i,j) 换成对角线索引 k = i + j，就会发现：
- 所有
k=0的状态（只有dp[0][0]）是边界，直接初始化； - 所有
k
