C++ Intuitive Solution Recursion With Memoization
Intuition\n\n At each point, we find what is the largest length square we can form, if we consider it as top left corner. \n A 3 length square, will also have a
**Intuition**\n\n* At each point, we find what is the largest length square we can form, if we consider it as top left corner. \n* A 3 length square, will also have a 2 length and 1 length square inside it.\nSo, we can simply add that length to our final answer.\n* So we can say that, \n**largest length square with i,j as top left** =  **total number of squares with i, j as top left**\n\n```\nclass Solution {\npublic:\n    int dp[301][301];\n    int dfs(vector<vector<int>>& A, int i, int j) {\n        if(i < 0 || j < 0 || i >= A.size() || j >= A[0].size() || A[i][j] != 1)\n            return 0;\n        if(dp[i][j] != -1)\n            return dp[i][j];\n        int ans = 1;\n        int l = dfs(A, i, j + 1), r = dfs(A, i + 1, j), t = dfs(A, i + 1, j + 1);\n        ans = 1 + min(l, min(r, t));\n        return dp[i][j] = ans;\n    }\n    \n    int countSquares(vector<vector<int>>& A) {\n        int ans = 0;\n        int n = A.size(), m = A[0].size();\n        vector<vector<int>> vis(n, vector<int>(m, 0));\n        memset(dp, -1, sizeof dp);\n        for(int i = 0; i < A.size(); i++) {\n            for(int j = 0; j < A[i].size(); j++) {\n                if(A[i][j]) {\n                    int sz = dfs(A, i, j); \n                    ans += sz;\n                }\n            }\n        }\n        return ans;\n    }\n};\n```
[]