[C++] O(n^2) explained with picture, beats 94% memory
\n\n\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<vector<int>>& pos) {\n        int n = pos.size();   \n        vector <int> h(n);    //h[i
![image](https://assets.leetcode.com/users/images/ae0a4c08-77a3-440f-8ca1-a8cf88ddee26_1660252409.4875157.png)\n\n```\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<vector<int>>& pos) {\n        int n = pos.size();   \n        vector <int> h(n);    //h[i] means the height at which the top surface of i-th block ends up \n        h[0] = pos[0][1];  //in the beginning it\'s obviously just the height of the first block because it is dropped at an empty surface\n        vector <int> ans(1, h[0]);  //and the first element of the answer is the same  \n        for (int i = 1; i < n; i++) {\n            int under = 0;  //the hight at which the i-th block will stop moving down. then h[i] = under + own height of the block\n            for (int j = 0; j < i; j++) {\n                bool ok = false;   // check if there is any previous block under the i-th block\n                if (pos[j][0] < pos[i][0]) {  //if the j-th block is to the left from the left side of the i-th block \n                    if (pos[j][0] + pos[j][1] > pos[i][0]) ok = true; //it\'s right point must be to the right side to overlap (case A)\n                }\n                else {   //if it\'s to the right, then it\'s left side should be to the left from the right side of the i-th block (case B)\n                    if (pos[j][0] < pos[i][0] + pos[i][1]) ok = true;\n                }\n                if (ok) under = max(under, h[j]);\n            }\n            h[i] = under + pos[i][1];\n            ans.push_back(max(ans.back(), h[i]));  \n        }\n        return ans; \n    }\n};\n```
['Dynamic Programming']