Algorithms first

编辑距离 · 交互式算法学习

求把 word1 转成 word2 的最少插入、删除、替换次数。

#72 · 多维动态规划

编辑距离

Edit Distance

测试用例word1 = "horse", word2 = "ros"

状态表3 个关键状态

进度 1 / 3速度

步骤 1状态 (5,3) 第一次计算。memo miss

∅ros∅

当前状态转移来源

演进 2

记忆化搜索

时间 O(mn)空间 O(mn)

仍沿用递归定义，但缓存 (i,j)，每个状态只计算一次。

1function minDistance(a, b) {2  const memo = new Map();3 4  function dfs(i, j) {5    const k = i + ',' + j;6    if (memo.has(k)) return memo.get(k);7    let ans;8    if (!i) ans = j;9    else if (!j) ans = i;10    else if (a[i - 1] === b[j - 1]) ans = dfs(i - 1, j - 1);11    else ans = 1 + Math.min(dfs(i, j - 1), dfs(i - 1, j), dfs(i - 1, j - 1));12    memo.set(k, ans);13    return ans14  }15  return dfs(a.length, b.length);16}

多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1class Solution {2    public int minDistance(String word1, String word2) {3        int m = word1.length(), n = word2.length();4        int[][] f = new int[m + 1][n + 1];5        for (int j = 1; j <= n; ++j) {6            f[0][j] = j;7        }8        for (int i = 1; i <= m; ++i) {9            f[i][0] = i;10            for (int j = 1; j <= n; ++j) {11                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {12                    f[i][j] = f[i - 1][j - 1];13                } else {14                    f[i][j] = Math.min(f[i - 1][j], Math.min(f[i][j - 1], f[i - 1][j - 1])) + 1;15                }16            }17        }18        return f[m][n];19    }20}

交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。

动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。

适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。

AlgoViz Lab

编辑距离 · 解法对比

AlgoViz Lab2026-07-112026-07-12

求把 word1 转成 word2 的最少插入、删除、替换次数。

测试用例: word1 = "horse", word2 = "ros"
题目分类: 多维动态规划
解法对比: 4

方案 1

朴素递归

末字符相同就共同前移；否则枚举插入、删除、替换三个分支。

时间: O(3^(m+n))
空间: O(m+n)

方案 2

记忆化搜索

仍沿用递归定义，但缓存 (i,j)，每个状态只计算一次。

时间: O(mn)
空间: O(mn)

方案 3

二维动态规划

dp[i][j] 表示前 i、j 个字符的距离，由左、上、左上转移。

时间: O(mn)
空间: O(mn)

方案 4

一维滚动 DP

当前行只依赖上一行和当前行左侧，用 prev 保存被覆盖的左上值。

时间: O(mn)
空间: O(n)