✅Easy DP Solution! Beats 100%! Concise explanation and visualization
\n# Approach\nLooking at the matrix we can figure a few things out -\n- A square submatrix can be formed if and only if we have a square submatrix in three dire
\n# Approach\nLooking at the matrix we can figure a few things out -\n- A square submatrix can be formed if and only if we have a square submatrix in three directions - top, left, diagonally left. i.e ```[i-1][j], [i][j-1] and [i-1][j-1]```.\n- A square submatrix formed is of size 1 + minimum size of the three submatrices.\n- And lastly but most importantly, a square matrix can be formed if and only if the current element is 1\n\nNow, we first copy our original matrix into dp matrix.\n```dp[i][j]``` represents the number of square submatrices ending at``` [i][j]```.\nThen we leave the first row and column as it is because the maximum size of square that can be formed will always be ```1``` in the first row and column, so we start from ```i=1 and j = 1```\n\nNow, ```check if the current element is 0```, if it is 0, it means we ```cannot have a submatrix``` ending at that position, if it is , it means we can have a submatrix, now the size of submatrix will be decided by ```1 + min(dp[i-1][j], dp[i][j-1] and dp[i-1][j-1])```. \n\nYou might notice we are here finding the size of matrix and not number of matrix, this is because the number of unique size matrix is our answer, so as we increment the ```min(dp[i-1][j], dp[i][j-1] and dp[i-1][j-1])``` we are basically, increasing the number of matrix by``` 1```.\n\nAt last go through the dp array again and store the values in ```answer```.\n\n# I\'ve explained the first test case below\n![image.png](https://assets.leetcode.com/users/images/76f1fc5e-9a1d-4ae4-811c-1c5f7b980d70_1694346512.2482584.png)\n\n\n# Code\n```\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        int m = matrix.size();\n        int n = matrix[0].size();\n\n        vector<vector<int>> dp = matrix;\n\n        for(int i = 1; i < m; i++){\n            for(int j = 1; j < n; j++){\n                if(matrix[i][j] != 0){\n                    dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) + 1;\n                }\n                \n            }\n        }\n        int answer = 0;\n        for(int i = 0; i < m; i++){\n            answer += accumulate(dp[i].begin(), dp[i].end(), 0);\n        }\n\n        return answer;\n    }\n};\n```
['C++']