使用滚动数组可将编辑距离空间复杂度降至O(n)，只需两个长度为n+1的一维数组prev和curr，初始化prev[i]=i；遍历source和target字符，按相等与否更新curr[j]；每行结束后交换prev与curr；最终返回prev[n]。

要计算两个字符串的编辑距离并节省内存，必须避开二维DP表的O(m×n)空间开销，改用滚动数组只保留两行状态——这是处理长字符串时避免栈溢出或内存超限的关键手段。

初始化一维滚动数组

声明两个长度为 【n+1】 的整型数组 prev 和 curr（n 为较短字符串长度），全部初始化为对应索引值：prev[i] = i，curr[0] = 0。这一步模拟了空字符串到 target[0..i-1] 的插入代价，不可跳过，否则后续递推全错。

分配数组时务必用 vector(n + 1) 或 new int[n + 1]，不能写成 vector(n)，否则访问 curr[n] 会越界。

逐行填充滚动状态

遍历 source 字符串每个字符 s[i]（i 从 1 到 m）→ 遍历 target 字符串每个字符 t[j]（j 从 1 到 n）→ 计算当前编辑距离：

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

立即学习“C++免费学习笔记（深入）”；

若 s[i-1] == t[j-1]，则 curr[j] = prev[j-1]；否则 curr[j] = min({prev[j], curr[j-1], prev[j-1]}) + 1。

内层循环结束后，交换 prev 与 curr 指针（或 swap(prev, curr)），使 prev 始终承载上一行结果。这一步必须在 j 循环外执行，否则下一轮 i 迭代将复用错误的历史行。

返回最终结果

外层循环结束后，prev[n] 即为完整编辑距离。直接 return prev[n]，无需额外判断或拷贝。