矩阵值相等时Needleman算法求解最长公共子序列(LCS)异常问题

• DP表填充逻辑错误
  Needleman-Wunsch算法要求每个单元格的取值为三个转移候选的最大值：

1. 左上角转移：两字符对齐，匹配加match、失配加mismatch
2. 上方转移：text2插入空位，加gap
3. 左方转移：text1插入空位，加gap
   原代码失配分支错误使用min计算两个空位候选的最小值，且匹配分支没有和空位转移候选比较最大值，不符合算法规则。

• 回溯逻辑遗漏对角转移路径
  原代码回溯仅在字符相等时走对角，其余场景仅比较上下方向的值，忽略了失配场景下也可能从对角转移的情况；同时多方向值相等时仅优先走左/上，会漏掉能命中匹配点的路径，这是ezu与ubm测试用例结果错误的直接原因。

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();
    
    vector<vector<int>> vec(m+1, vector<int>(n+1,0));
    int mismatch  = -3;
    int gap = -4;
    int match = 1;
    
    for (int i = 1; i <= m; i++) {
        vec[i][0] = vec[i-1][0] + gap;
    }
    
    for (int i = 1; i <= n; i++) {
        vec[0][i] = vec[0][i-1] + gap;
    }
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            // 计算三个候选值
            int diag = vec[i-1][j-1] + (text1[i-1] == text2[j-1] ? match : mismatch);
            int up = vec[i-1][j] + gap;
            int left = vec[i][j-1] + gap;
            // 取最大值作为当前单元格值
            vec[i][j] = max(max(diag, up), left);
        }
    }
    
    int matchLen = 0;
    int i = m;
    int j = n;
    
    while (i >0 && j >0) {
        if (text1[i-1] == text2[j-1] && vec[i][j] == vec[i-1][j-1] + match) {
            // 匹配场景，走对角
            matchLen++;
            i--;
            j--;
        } else {
            // 优先判断是否从对角转移（失配场景）
            int diag = vec[i-1][j-1] + (text1[i-1] == text2[j-1] ? match : mismatch);
            if (i > 0 && j > 0 && vec[i][j] == diag) {
                i--;
                j--;
            } else if (i > 0 && vec[i][j] == vec[i-1][j] + gap) {
                // 从上方转移
                i--;
            } else {
                // 从左方转移
                j--;
            }
        }
    }
    return matchLen;
}

修正后测试text1 = "ezu"、text2 = "ubm"场景，回溯路径会正确走到匹配点[3,1]，返回结果为1，符合LCS预期。

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