C++ 2-D DP solution
We will use the same input array for computation. We will update the cells in this array as number of square submatrices with their bottom right corner as the c
We will use the same input array for computation. We will update the cells in this array as number of square submatrices with their bottom right corner as the current cell.\nAs we need square submatrices, the row=0 and col=0 need not to be processed. Now looking at every other cells of original matrix, we check the value of the cell:\n1. If it is 0, we dont need to bother, as it can be part of 0 square submatrices\n2. If it is 1, we need to check the cells- [i-1][j-1], [i][j-1], [i-1][j]. We need minimum of this, because we can only have that many square submatrices (of size greater than 1x1) with current cell as bottom right corner. For example,\n 0 | 1\n 1 | 1\n lets say we have this formation, at position (1, 1), there can be no square submatrix of size greater than 1.\n We also add 1 at last to include the square submatrix of size 1x1.\n```\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        int m = matrix.size(), n = matrix[0].size();\n        for(int i=1; i<m; i++)\n        {\n            for(int j = 1; j<n; j++)\n            {\n                if(matrix[i][j]==1)\n                    matrix[i][j] = min({matrix[i-1][j], matrix[i][j-1], matrix[i-1][j-1]}) + 1;\n            }\n        }\n        int count=0;\n        for(int i=0; i<m; i++)\n        {\n            for(int j=0; j<n; j++)\n                count+=matrix[i][j];\n        }\n        return count;\n    }\n};\n```
['Dynamic Programming', 'C', 'C++']