[C++] O(MN) DP solution, beats 100% in memory. [Detailed Explanation]
\n/*\n    https://leetcode.com/problems/count-square-submatrices-with-all-ones/\n*/\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix
```\n/*\n    https://leetcode.com/problems/count-square-submatrices-with-all-ones/\n*/\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        // We use the grid to store the length of maximum \n        // square ending at (i, j).\n        int total_sq = 0;\n        \n        // 1st row: add the 1 length squares\n        for(int i = 0; i < matrix[0].size(); i++)\n            if(matrix[0][i])\n                ++total_sq;\n        \n        // 1st col: add the 1 length squares\n        for(int i = 1; i < matrix.size(); i++)\n            if(matrix[i][0])\n                ++total_sq;\n        \n        for(int i = 1; i < matrix.size(); i++)\n            for(int j = 1; j < matrix[0].size(); j++) {\n                // if the current pos is 1\n                if(matrix[i][j]) {\n                    matrix[i][j] = min({matrix[i-1][j-1],\n                                            matrix[i][j-1],\n                                            matrix[i-1][j]});\n                    \n                    // if the square ending at (i, j) has length 0,\n                    // with the adjacent blocks, we can still make a sq of length 1\n                    // since the current pos is 1\n                    matrix[i][j] += 1;\n                    total_sq += matrix[i][j];\n                }\n            }\n             \n         \n        return total_sq;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']