[C++] DP solution with space optimized


  • 1
    I

    For the regular DP solution, we'd need a 2D array of size m*n where m is the size of array A and n is the size of array B. However, when I had code like this:

    vector<vector<int>> dp (m+1, vector<int> (n+1, 0));
    

    I got an Memory Limit Exceeded error, I suppose it's because for some test cases, this caused stack to overflow. This problem can be addressed by allocating the 2D array on heap instead of stack:

    auto dp_ptr = new vector<vector<int>>(m+1, vector<int> (n+1, 0));
    auto dp = *dp_ptr;
    

    However, for this problem, we don't have to use a 2D array actually. A 1D array is good enough since we only need to find out the maximum length of the repeated subarray of A and B. Here is how: we just need to pick an array of shorter length, say n < m, so B is shorter, then allocating a 1D array:

    vector<int> dp (n+1, 0);
    

    For any i where 0 < i < m, dp[j] means the maximum length of repeated subarray ends at A[i] and B[j-1]. So dp[j] = 0 if A[i] != B[j-1] and dp[j] = 1 + dp[j-1] if A[i] == B[j-1], note here dp[j-1] means the maximum length of repeated subarray ends at A[i-1] and B[j-2], it was computed when i was i - 1.

    Below is the full code:

    class Solution3 {
    private:
      // A.size >= B.size
      int _findLength(vector<int>& A, vector<int>& B) {
        int m = A.size();
        int n = B.size();
        int max_len = 0;
    
        vector<int> dp (n+1, 0);
        for (int i = 0; i < m; ++i) {
          for (int j = n; j >= 1; --j) {
            if (B[j-1] == A[i]) dp[j] = 1 + dp[j-1]; 
            else dp[j] = 0;
            max_len = max(max_len, dp[j]);
          }
        }
    
        return max_len;
      }
    
    public:
      int findLength(vector<int>& A, vector<int>& B) {
        int max_len;
    
        if (B.size() <= A.size()) {
          max_len =_findLength(A, B);
        } else {
          max_len =_findLength(B, A);
        }
    
        return max_len;
      }
    };
    

Log in to reply
 

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