递归+记忆化实现LCS代码异常求助：大字符串结果错误

问题描述 #

尝试用递归+记忆化结合哈希表实现最长公共子序列（LCS），已知DP方法更高效，仅作学习用途。实现思路是用to_string(x)+"@@"+to_string(y)作为哈希表的键存储子问题结果。

编写的C++代码如下：

int lcsRecursiveAndMemorization(std::string S1, std::string S2, std::unordered_map<std::string, int> &um, int x, int y)
{
    // if either string is empty 
    if (x == -1 || y == -1)
    {
        return 0;
    }

    // check if it is present already
    std::string temp = std::to_string(x) + "@@" + std::to_string(y);
    if (um.find(temp) != um.end())
    {
        return um[temp];
    }
    else
    {
        // check for if both the characters are equal
        if (S1[x] == S2[y])
        {
            // after getting answer store it and then return it.
            std::string temp1 = std::to_string(x - 1) + "@@" + std::to_string(y - 1);
            um[temp1] = 1 + lcsRecursiveAndMemorization(S1, S2, um, x - 1, y - 1);
            return um[temp1];
        }
        else
        {
            // store answer for all the cases i.e.,
            // for x-1, y and x, y-1
            // and for x, y also
            std::string temp2 = std::to_string(x - 1) + "@@" + std::to_string(y);
            std::string temp3 = std::to_string(x) + "@@" + std::to_string(y - 1);

            int first_ = lcsRecursiveAndMemorization(S1, S2, um, x - 1, y);
            int second_ = lcsRecursiveAndMemorization(S1, S2, um, x, y - 1);

            // storing
            um[temp2] = first_;
            um[temp3] = second_;
            um[temp] = std::max(first_, second_);
            return um[temp];
        }
    }
}

int main()
{
    std::string S2 = "pmjghexybyrgzczy";
    std::string S1 = "hafcdqbgncrcbihkd";
    int x = S1.size() - 1;
    int y = S2.size() - 1;

    std::unordered_map<std::string, int> um;
    cout << "The LCS length using recursion + memorization is -> " << lcsRecursiveAndMemorization(S1, S2, um, x, y) << "\n";
    return 0;
}

该代码对短字符串计算正确，但处理长字符串时结果错误。例如测试用例中正确结果应为4，程序输出5；但交换S1和S2后结果正确。

错误根源 #

核心问题出在字符相等的分支中，未存储当前(x,y)对应的子问题结果：
当S1[x] == S2[y]时，当前子问题的结果是1 + lcs(x-1,y-1)，但代码仅将该值存入了x-1,y-1对应的键下，完全遗漏了把当前x,y的键temp与结果关联的步骤。

这会导致后续若有其他子问题需要查询(x,y)的结果时，哈希表中无对应记录，会触发重复递归计算。长字符串中子问题重复查询次数多，重复计算的递归路径可能偏离正确逻辑，最终得出错误结果。交换S1和S2后结果正确只是巧合——此时递归路径的子问题查询顺序刚好未触发这个漏洞，并非根本解决办法。

修正后的代码 #

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

int lcsRecursiveAndMemorization(std::string S1, std::string S2, std::unordered_map<std::string, int> &um, int x, int y)
{
    // 边界条件：任一字符串为空
    if (x == -1 || y == -1)
    {
        return 0;
    }

    std::string temp = std::to_string(x) + "@@" + std::to_string(y);
    // 检查当前子问题是否已缓存
    if (um.find(temp) != um.end())
    {
        return um[temp];
    }

    int result;
    if (S1[x] == S2[y])
    {
        result = 1 + lcsRecursiveAndMemorization(S1, S2, um, x - 1, y - 1);
    }
    else
    {
        int first_ = lcsRecursiveAndMemorization(S1, S2, um, x - 1, y);
        int second_ = lcsRecursiveAndMemorization(S1, S2, um, x, y - 1);
        result = std::max(first_, second_);
    }

    // 关键：无论分支逻辑如何，都缓存当前子问题的结果
    um[temp] = result;
    return result;
}

int main()
{
    std::string S2 = "pmjghexybyrgzczy";
    std::string S1 = "hafcdqbgncrcbihkd";
    int x = S1.size() - 1;
    int y = S2.size() - 1;

    std::unordered_map<std::string, int> um;
    cout << "The LCS length using recursion + memorization is -> " << lcsRecursiveAndMemorization(S1, S2, um, x, y) << endl;
    return 0;
}

修正说明 #

1. 用统一的result变量存储当前子问题结果，避免分支逻辑中存储规则混乱；
2. 无论字符是否相等，计算完成后都将当前(x,y)对应的结果存入哈希表，确保后续子问题可直接复用，杜绝重复计算引发的错误；
3. 移除了原代码中多余的提前存储子问题逻辑（如手动存储x-1,y-1等），递归调用会自动处理子问题的缓存，无需提前手动干预，简化逻辑同时避免冗余错误。

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