# LCS , C++ concise primary and optimized O(n) space solution

• ①dp[i][j] represents the largest common substring between vector v1 ends with i index and v2 end with j index.
②In c++, former answer will get memory exceed limit,but we find that dp[i][j] has relation only with last dp[i-1][j-1],so we can use dp[j] to represent last row dp and use now[j] to represent current row answer.
Hope it can give you some help.

``````int findLength(vector<int>& A, vector<int>& B) {
int m=A.size(),n=B.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));int r=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(A[i-1]==B[j-1])dp[i][j]=dp[i-1][j-1]+1,r=max(r,dp[i][j]);
}
}
return r;
}
``````
``````int findLength(vector<int>& A, vector<int>& B) {
int m=A.size(),n=B.size();
vector<int> dp(n+1,0);int r=0;
for(int i=1;i<=m;i++){
vector<int> now(n+1,0);
for(int j=1;j<=n;j++){
if(A[i-1]==B[j-1])now[j]=dp[j-1]+1,r=max(r,now[j]);
}
dp=now;
}
return r;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.