I'm trying to solve Ones and Zeros question from leetcode and for the same code but using vector occupies ~3x more memory than using array of same size. Here is my code that uses 3-D vector:

int findMaxForm(vector<string>& strs, int m, int n) {
    int S = strs.size();
    vector<vector<vector<int>>> dp(S 1, vector<vector<int>>(m 1, vector<int>(n 1, 0)));

    // int dp[S 1][m 1][n 1];
    // memset(dp, 0, sizeof dp);
    
    for(int i = 0; i < S; i  ) {
        for(int j = 0; j <= m; j  ) {
            for(int k = 0; k <= n; k  ) {
                if(i == 0) {
                    int zeros = count(strs[i].begin(), strs[i].end(), '0');
                    int ones = strs[i].length() - zeros;

                    if(zeros <= j && ones <= k) dp[i][j][k] = 1;
                    else dp[i][j][k] = 0;
                    continue;
                }
                int skip = dp[i - 1][j][k];
    
                int take = INT_MIN;
                int zeros = count(strs[i].begin(), strs[i].end(), '0');
                int ones = strs[i].length() - zeros;
                if(zeros <= j && ones <= k)
                    take = 1   dp[i - 1][j - zeros][k - ones];

                dp[i][j][k] = max(skip, take);
            }
        }
    }
    
    return dp[S-1][m][n];
}

Submission details:

• Using vector: Runtime (~500ms); Memory (102.6 MB)
• Using array: Runtime (~500ms); Memory (32.5 MB)

CodePudding user response：

An array (I assume you used plain C arrays) uses only as much memory as its elements. A vector uses some memory to store some housekeeping information like the length and location of the data.

Because you made a vector of vector of vectors, this housekeeping information is created for all of the nested vectors, which occupies a lot of space. This gets worse and worse if you increase the "dimension" of your "multidimensional" vector.