C++实现LCS时字符串值传递超时 引用传递正常原因排查

问题现象 #

实现基于递归+记忆化动态规划的最长公共子序列（LCS）C++代码时，仅修改递归工具函数的字符串参数传递方式，就出现了巨大的性能差异：

• 字符串参数使用*引用传递（string&）*时，代码可正常运行，通过全部测试用例
• 移除引用修饰改为*值传递（string）*时，代码触发时间限制超出错误，无法通过测试

不同传参方式的代码实现 #

可正常运行的引用传参版本 #

class Solution {
public:
    int lcsUtil(string& s1,int ind1,string& s2,int ind2,vector< vector<int>>&dp){
        if(ind1<0 || ind2<0) return 0;
        
        if(dp[ind1][ind2] != -1) return dp[ind1][ind2];
        
        if(s1[ind1] == s2[ind2])
            return dp[ind1][ind2] = 1 + lcsUtil(s1,ind1-1,s2,ind2-1,dp);
        
        else 
            return dp[ind1][ind2] = 0 + max(lcsUtil(s1,ind1-1,s2,ind2,dp),lcsUtil(s1,ind1,s2,ind2-1,dp));
    }
    int longestCommonSubsequence(string text1, string text2) {
        vector< vector<int> > dp (text1.size(),vector<int>(text2.size(),-1));
        return lcsUtil(text1,text1.size()-1,text2,text2.size()-1,dp);

    }
};

触发超时的值传参版本 #

class Solution {
public:
    int lcsUtil(string s1,int ind1,string s2,int ind2,vector< vector<int>>&dp){
        if(ind1<0 || ind2<0) return 0;
        
        if(dp[ind1][ind2] != -1) return dp[ind1][ind2];
        
        if(s1[ind1] == s2[ind2])
            return dp[ind1][ind2] = 1 + lcsUtil(s1,ind1-1,s2,ind2-1,dp);
        
        else 
            return dp[ind1][ind2] = 0 + max(lcsUtil(s1,ind1-1,s2,ind2,dp),lcsUtil(s1,ind1,s2,ind2-1,dp));
    }
    int longestCommonSubsequence(string text1, string text2) {
        vector< vector<int> > dp (text1.size(),vector<int>(text2.size(),-1));
        return lcsUtil(text1,text1.size()-1,text2,text2.size()-1,dp);

    }
};

性能差异根本原因 #

性能差异完全来自C++值传递和引用传递的语义区别，和动态规划逻辑本身无关：

• 值传递会产生全量对象拷贝开销：std::string是典型的值语义类型，参数按值传递时，每次函数调用都会为传入的字符串生成一份完整拷贝：需要申请新的堆内存、逐字符复制全部内容、函数退出时还要调用析构函数释放拷贝的内存，单次拷贝两个字符串的时间复杂度为O(m+n)（m、n分别为两个输入串的长度）。
• 递归调用量级放大拷贝开销：记忆化版本的LCS递归总调用次数为O(mn)（dp数组共mn个独立状态，每个状态至少触发1次函数调用，加上分支递归的调用总次数仍是mn量级）。如果每次调用都要执行O(m+n)的字符串拷贝，总时间复杂度会从引用传递版本的O(mn)* 直接飙升到 O(mn(m+n))*。

举个直观例子：当两个输入串长度均为1000时，引用传递版本总操作量约1e6，完全符合常规算法题的时间限制；值传递版本总操作量会达到2e9级别，远超CPU每秒的运算能力，必然触发超时。

• 记忆化无法抵消值传递开销：记忆化的作用是缓存已计算的状态结果、避免重复的状态逻辑计算，但只要发生函数调用，值传递的参数拷贝动作就会在函数逻辑执行前完成，哪怕是直接返回缓存值的调用，也会产生全额的字符串拷贝开销，这部分损耗完全无法被优化。
• 引用传递无额外拷贝成本：使用string&传参时，所有递归调用都直接引用外层函数的原始字符串对象，不会触发任何内存申请、内容拷贝、对象析构的额外操作，总时间复杂度稳定保持O(mn)，因此可以正常通过所有测试用例。

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