Simple DP solution With detail Explanation || C++
Simple intuation is minimum size square will be formed by only one cell of 1 in order to make sqaure of size 2 we need 3 cells of 1 i.e,\ndp[i][j] means the siz
Simple intuation is minimum size square will be formed by only one cell of 1 in order to make sqaure of size 2 we need 3 cells of 1 i.e,\ndp[i][j] means the size of biggest square with A[i][j] as bottom-right corner.\ndp[i][j] also means the number of squares with A[i][j] as bottom-right corner.\n\nIf A[i][j] == 0, no possible square.\nIf A[i][j] == 1,\n\nSame exaplantion with picture : \n![image](https://assets.leetcode.com/users/images/e4cc10cf-8d09-47ed-9840-704a0778f3f2_1648785730.4369748.png)\n\n\nwe compare the size of square dp[i-1][j-1], dp[i-1][j] and dp[i][j-1].\nmin(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1 is the maximum size of square that we can find.\n\n![image](https://assets.leetcode.com/users/images/cf848be3-29af-4d81-bc26-424848c80a82_1648785802.8151166.png)\n\n**Input**: matrix =\n[\n  [0,1,1,1],\n  [1,1,1,1],\n  [0,1,1,1]\n]\n\n**Dp matrix :**\n0 0 0 0 0 \n0 0 1 1 1 \n0 1 1 2 2 \n0 0 1 2 3 \n\nNow we just need to simply compute the sum of all cells present in dp:\n**Time complexity : N^2**\n**Space Complexity: N^2**\n**Note :** we can easly optimized the space by making the required changes in given matrix only.\n\nSimlier Question to practice: https://leetcode.com/problems/maximal-square/\n\n\n**Complete Code**\n\n\n```\nint countSquares(vector<vector<int>>& matrix) {\n         int m = matrix.size();\n        if(m==0) return 0;\n        int n = matrix[0].size();\n        int result = 0;\n        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));\n\n        int ret = 0;\n        for(int i = 1; i <= m; i ++){\n            for(int j = 1; j <= n; j ++){\n                if(matrix[i-1][j-1] == 0){\n                    dp[i][j] = 0;\n                }else{\n                    dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]));\n                }\n                result += dp[i][j];\n            }\n        }\n\n        return result;\n    }\n```\n\n
['Dynamic Programming', 'C']