为什么我会得TLE

Question

问题：我在这个LEETCODE问题中得到了一个TLE，即寻找最长的公共子序列。通过了42/45个测试用例。请帮忙。您可以复制以下关于LEETCODE 1143问题的代码，并在可能的情况下提供帮助：

//求解(i，j(->分别表示字符串text1和text2中直到索引i和j的LCS的长度。

int solve(string text1, string text2,int i,int j,int dp[1001][1001]){
//base case
if(i<0||j<0){
return 0 ;
}
if(dp[i][j]!=-1) {
return dp[i][j];
}
else{
if(text1[i]==text2[j]){
return dp[i][j] = 1+ solve(text1,text2,i-1,j-1,dp) ;                                
}

else{
return dp[i][j] = max(solve(text1,text2,i,j-1,dp),solve(text1,text2,i-1,j,dp));
}
}
}
int longestCommonSubsequence(string text1, string text2) {
int m=text1.size();
int n=text2.size();

int dp[1001][1001];
memset(dp,-1,sizeof(dp));

return solve(text1,text2,m-1,n-1,dp);
}

Answer 1

TLE的原因是solve递归效率不高。递归发生两次(此处：max(solve(text1,text2,i,j-1,dp),solve(text1,text2,i-1,j,dp))(。试着找到一个更有效的算法。

我只会遍历矩阵，而不是递归，只是不按行或列，而是按对角线。

较小的改进是通过引用传递字符串(因此string&而不仅仅是string(。