有啥错误吗？不能编译

幽灵特工 @ 2020-09-09 20:41:25

#include <bits/stdc++.h>
using namespace std;
int n;
int s1[100003],s2[100003];
int dp[100003][100003]={0};
int LCS(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(s1[i]==s2[j])dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[n-1][n-1];
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s1[i];
    }
    for(int i=0;i<n;i++){
        cin>>s2[i];
    }
    cout<<LCS();
}

by rui_er @ 2020-09-09 20:42:34

@幽灵特工 您 dp 开太大了，肯定编译不了

by SteveFang @ 2020-09-09 20:43:11

数组开太大了

by 幽灵特工 @ 2020-09-09 20:44:31

@SteveFang 那应该怎么办呢？

by SteveFang @ 2020-09-09 20:45:30

@幽灵特工 优化空间复杂度啊，你这 n^2 怎么可能过？重新写方程吧

by 幽灵特工 @ 2020-09-09 20:45:52

@SteveFang 好的，谢谢！

by 旭日临窗 @ 2020-09-09 20:49:44

@幽灵特工 这题就不是最长公共子序列的题，考的是最长上升子序列

by fast_photon @ 2020-09-26 16:26:25

滚动使用dp就能编译了，把所有dp调用第一个下标为i的改成i%2，同理把所有dp调用第一个下标为i-1的改成(i-1)%2
最后输出改成dp[(n-1)%2][n%2]
这个东东支持markdown诶

by fast_photon @ 2020-09-26 16:27:49

@fast_photon
纠正一下自己，dp[(n-1)%2][n-1]

by fast_photon @ 2020-09-26 16:29:20

补充一下，定义的时候改成dp 2 100003就OK了

by rickyxrc @ 2021-02-01 11:51:50

您的代码：int dp[100003][100003]={0};无法通过编译，可以这样改:int dp[2][100001]（滚动）