Three methods declare 2d array in CPP, whose memory consumption differ significantly.
Rush
165
CC++Dynamic Programming

When I try solve Longest Palindromic Substring, I declare a 2d array using three methods:

  1. vector
  2. new
  3. VLA (cpp standard don't support vla, but compiler(g++/clang++) can accept it as valid syntax)

For the same data scale, after many tests, VLA just need about 11MB memory, but vector and new always consume 380MB+ memory, what caused it differ in memory consumption?

As I known, VLA allocate memory in stack, and new allocate in heap.
image

My code:

//https://leetcode.com/problems/longest-palindromic-substring/
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if(len < 2)
            return s;
        // 1.
        vector<vector<int>> dp(len, vector<int>(len, 0));
        // 2.
        // int **dp = new int* [len];
        // for(int i = 0; i < len; i++)
        //     dp[i] = new int[len];
        // 3.
        // int dp[len][len];

        for(int i = 0; i < len; i++)
            dp[i][i] = 1;
        int maxlen = 1, maxI = 0;
        for(int r = 1; r < len; r++){
            for(int l = 0; l < r; l++) {
                if(s[l] != s[r])
                    dp[l][r] = 0;
                else if(r - l < 3)
                    dp[l][r] = 1;
                else 
                    dp[l][r] = dp[l + 1][r - 1];
                if(dp[l][r] && r - l + 1 > maxlen) {
                     maxlen = r - l + 1;
                     maxI = l;
                }
            }
        }
		// 2.
        // for(int i = 0; i < len; i++)
        //     delete[] dp[i];
        // delete [] dp;
        return s.substr(maxI, maxlen);
    }
};
Comments (0)