Why my dp solution get memory exceed limit error?


  • 2
    X

    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[][].


  • 0
    M

    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.


  • 0
    J

    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;
        }
    

  • 0
    M

    @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.


  • 0

    We have just finish rejudged all affected submissions. The scoreboard is being updated as well.


Log in to reply
 

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