If using vector<vector<int>> dp to store the result, I get memory exceed limit error, while using int[][] dp, my submission is accepted.
I am wondering why vector<vector<int>> consumes more memory than int[][].
I had a similar issue: https://discuss.leetcode.com/topic/108778/unexpected-memory-limit-exceeded-possible-leetcode-bug
I hope an admin can look into this, as it also affected my rank.
In C++, vector do cost more space than an int array.
For this problem, to handle MLE, you can use the strategy called "rolling array".
Since for the dp formula, dp[i][j] only need the information of dp[i-1][j-1], so you can always use an extra tmp var to store it and update in the fly.
My code here:
int findLength(vector<int>& A, vector<int>& B) {
int m = A.size(), n = B.size(), ans = 0, tmp = 0, cur;
vector<int> dp(n+1, 0);
for(int i = 1; i <= m; ++i){
tmp = 0;
for(int j = 1; j <= n; ++j){
cur = dp[j];
if(A[i-1] == B[j-1])
dp[j] = 1 + tmp;
else
dp[j] = 0;
tmp = cur;
ans = max(ans, dp[j]);
}
}
return ans;
}
@JadenPan This doesn't explain why similar Java and Python solutions (which use even more space than nested vectors) do not get MLE, or why moving the vectors to the global scope prevents MLE.