面试题库 › 算法 / 大模型 › DTW 算法原理及与 NW 算法对比

DTW 算法原理及与 NW 算法对比

难度 ★★★在 2 场真实面经中被问到 方向:算法 / 大模型考点:动态规划

哪些公司问过

美团1字节跳动1

常见岗位:人工智能、机器学习算法(泛)

答案要点

  1. DTW 衡量时间轴可伸缩的序列相似度,允许一对多对齐
  2. DP:D[i][j] = d(i,j) + min(D[i-1][j], D[i][j-1], D[i-1][j-1]),结果取右下角
  3. 约束:边界、单调性、连续性;复杂度 O(nm),可加窗口约束加速
  4. NW:全局序列比对,匹配/错配得分加空位罚分,求最大得分,类似编辑距离
  5. 异同:都是二维 DP 加回溯;DTW 无空位且最小化距离,NW 有空位罚分

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题