DTW 算法原理及与 NW 算法对比
哪些公司问过
答案要点
- DTW 衡量时间轴可伸缩的序列相似度,允许一对多对齐
- DP:D[i][j] = d(i,j) + min(D[i-1][j], D[i][j-1], D[i-1][j-1]),结果取右下角
- 约束:边界、单调性、连续性;复杂度 O(nm),可加窗口约束加速
- NW:全局序列比对,匹配/错配得分加空位罚分,求最大得分,类似编辑距离
- 异同:都是二维 DP 加回溯;DTW 无空位且最小化距离,NW 有空位罚分
易错点
- 把 DTW 当成要求两序列等长的逐点欧氏距离
- 说 NW 和 DTW 完全一样,忽略空位罚分与目标方向的差异
- 忽略窗口约束,长序列时复杂度过高或出现病态对齐
面试官常见追问
- 为什么项目要用硬对齐 DTW,而不用 soft-DTW?
- DTW 满足距离的三角不等式吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 最长递增子序列(LIS)27 场
- 动态规划的基础与解题流程26 场
- 爬楼梯(青蛙跳台阶)18 场
- 不同路径(网格路径数)17 场
- 买卖股票的最佳时机16 场
- 编辑距离的动态规划解法16 场
- 零钱兑换:最少硬币数与组合数12 场
- 最长公共子序列(LeetCode 1143)11 场
- 矩阵最小路径和(动态规划)10 场
- 斐波那契数列的几种解法8 场