为什么即使我使用记忆化也会出现 TLE？

Question

这里是问题陈述

给定两个字符串 s1 和 s2，return 它们最长公共子序列的长度。

字符串的子序列是从原始字符串中删除一些字符（可以是none）而不改变其余字符的相对顺序而生成的新字符串。（例如，“ace”是“abcde”的子序列，而“aec”不是）。两个字符串的公共子序列是两个字符串共有的子序列。

如果没有公共子序列，return0.

这是我的代码

class Solution {
public:
    int dp[1001][1001];
    int lcs(string s1,string s2,int n,int m){
        if (n==0 || m == 0)
            return 0;
        if(dp[n][m]!=-1)
            return dp[n][m];
        if (s1[n-1] == s2[m-1])
        {
            return dp[n][m]=  1 + lcs(s1,s2,n-1,m-1);
        }
        else
        {
            return dp[n][m]= max(lcs(s1,s2,n-1,m), lcs(s1,s2,n,m-1));
        }
        return dp[n][m];
    }
    int longestCommonSubsequence(string s1, string s2) {
        memset(dp,-1,1001*1001*sizeof(int));
        return lcs(s1,s2, s1.size(), s2.size());
        
    }
};

谢谢

Answer 1

在函数定义中使用引用调用而不是值调用。

int lcs(string &s1,string &s2,int n,int m);

int longestCommonSubsequence(string &s1, string &s2);

Answer 2

您的实施至少有 2 处可以进一步改进。

您正在使用递归算法，将其重写为迭代版本
您正在使用 1001*1001 数组，因此您在一定程度上破坏了缓存

存在更space有效的算法，Hirschberg's algorithm，只返回 LCS 的长度。

为什么即使我使用记忆化也会出现 TLE？

Why I'm getting TLE even if I'm using memoization?

c++

recursion

memoization

cp