C语言实现动态规划编辑距离 输出结果偏差问题排查

核心问题根源 #

代码混同了递归遍历、循环遍历、记忆化存储三层逻辑，导致计算结果和真实最优解出现偏差，具体分为三点：

• 相同字符的匹配逻辑完全偏离递推规则
  正常编辑距离的递推规则为：当str1[i] == str2[j]时，该位置不需要额外操作，最优值等于i+1,j+1位置的子问题结果。但原代码遇到相同字符时，直接在当前循环里移动i、j指针，既不将该状态的结果存入dp记忆数组，也不触发该子问题的递归计算，相当于丢失了该状态下所有分支的最优选择，只沿着指针移动的单一路径累计步数。
• 递归返回值与循环累计的steps逻辑完全割裂
  原代码在计算完ans1（删除str1当前字符）、ans2（删除str2当前字符）、ans3（替换两个当前字符）三个子问题的最小值后，将结果存入dp数组，但后续主流程仍通过while循环手动移动指针、累加steps作为最终返回值，完全没有使用已经计算好的记忆化结果。这也是为什么部分测试用例（如short和ports）能得到正确结果——这类用例的单循环路径恰好和全局最优解重合，而editing和distance的最优解不在单循环路径上，就会出现计算值偏大的问题。
• 边界条件的返回值计算不准确
  原代码没有在递归入口判断边界场景，而是靠while循环逐位移动指针累计剩余字符的步数，导致子问题的返回值不是严格的剩余字符串长度，存在累计偏差。

简化修正后的代码 #

去掉冗余的循环逻辑，保留递归+记忆化的标准编辑距离实现：

#include <stdio.h>
#include <string.h>

int check(const char* str1, const char* str2, int i, int j, int dp[10][10])
{
    // 边界条件：str1走到末尾，剩余str2的字符全是需要插入的操作数
    if (str1[i] == '\0') {
        return (int)strlen(str2) - j;
    }
    // 边界条件：str2走到末尾，剩余str1的字符全是需要删除的操作数
    if (str2[j] == '\0') {
        return (int)strlen(str1) - i;
    }
    // 直接返回记忆化存储的子问题结果
    if (dp[i][j] != -1) {
        return dp[i][j];
    }
    // 字符相同，不需要额外操作，直接取i+1,j+1的子问题结果
    if (str1[i] == str2[j]) {
        dp[i][j] = check(str1, str2, i+1, j+1, dp);
        return dp[i][j];
    }
    // 三个分支取最小值，每个分支对应1次操作
    int ans1 = check(str1, str2, i+1, j, dp);   // 删除str1当前字符
    int ans2 = check(str1, str2, i, j+1, dp);   // 删除str2当前字符
    int ans3 = check(str1, str2, i+1, j+1, dp); // 替换当前两个字符
    int min = ans1 < ans2 ? ans1 : ans2;
    min = min < ans3 ? min : ans3;
    dp[i][j] = min + 1;
    return dp[i][j];
}

int main() {
    char str1[10] = "editing";
    char str2[10] = "distance";
    int min_step[10][10];
    memset(min_step, -1, sizeof(min_step));
    printf("%d\n", check(str1, str2, 0, 0, min_step));
    return 0;
}

修正后运行代码，editing和distance的计算结果为5，和预期值一致。

内容的提问来源于stack exchange，提问作者keitou777