编辑距离动态规划状态定义为dpi表示str1前i字符变str2前j字符的最少操作数，其中i、j为长度，数组大小为(m+1)×(n+1)，初值dp0=j、dpi=i。
编辑距离的动态规划状态怎么定义
编辑距离本质是把 str1 变成 str2 所需的最少单字符操作数（插入、删除、替换）。动态规划的核心是定义 dp[i][j]：表示 str1 的前 i 个字符变成 str2 的前 j 个字符所需的最小操作数。
注意下标含义——i 和 j 是长度，不是索引，所以 dp 数组大小应为 (m+1) × (n+1)（m = str1.size(), n = str2.size()），且 dp[0][j] = j、dp[i][0] = i 是合法初值（空串变长度为 j 的串只能插入 j 次）。
状态转移方程怎么写才不出错
关键在比较 str1[i-1] 和 str2[j-1]（因为 i、j 是长度，对应字符索引要减 1）：
- 如果相等：
dp[i][j] = dp[i-1][j-1]（无需操作） - 如果不等：
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1
其中：dp[i-1][j] 对应删除 str1[i-1]，dp[i][j-1] 对应在 str1 末尾插入 str2[j-1]，dp[i-1][j-1] 对应把 str1[i-1] 替换为 str2[j-1]。三者取最小再加 1，就是当前最优解。
常见错误是混淆索引导致越界或漏掉 +1，或者误把 dp[i][j-1] 理解为“删除”，实际它对应插入——逻辑必须和操作语义严格对齐。
能不能只用一维数组节省空间
可以，但要注意覆盖顺序。因为 dp[i][j] 只依赖上一行（i-1）和当前行左侧（j-1），所以用一维 vector 即可：
- 初始化：
dp[j] = j（第 0 行） - 外层循环
i从 1 到m，内层j从 1 到n - 需要缓存左上角旧值：
int prev = dp[0]; dp[0] = i;，然后每步更新前保存dp[j]到temp，更新后用prev参与计算
空间从 O(mn) 降到 O(n)，但代码可读性下降，调试时容易因缓存错位导致结果偏小——比如忘记在每轮开始重置 prev，就会复用上轮残留值。
边界和字符集有没有隐藏坑
标准编辑距离假设所有字符操作代价为 1，不区分大小写需提前 transform；若字符串含 Unicode（如 UTF-8 中文），直接按 char 遍历会切碎多字节序列，此时不能用 string::size() 当字符数，得先转 std::u32string 或用 ICU 库拆分码点。
另外，某些场景要求不同操作代价不同（如替换比删除便宜），这时要把 +1 换成对应权重变量，且初值也要按权重初始化（如 dp[0][j] = j * insert_cost）。
真正上线时，别直接套模板——先用两个短字符串（如 "ab" 和 "a"）手推几轮 dp 表，确认第一行、第一列、对角线更新都符合直觉，再跑代码。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
