3 Solutions - Recursion | Memoization | Tabulation - Easy to Understand
 \n\nInput used in demonstration:\n[[1,0,1,0,0,0,0], [1,1,1,1,1,0,0],[1,1,1,1,1,0,1],[0,0,1,1,1,1,0], [1,1,0,0,1,1,0],[0,0,0,0,1,1,0],[1,1,0,1,0,1,1]]\n\nApproa
<img src="https://assets.leetcode.com/users/images/3009c05e-32f3-4f01-9946-0a48ab0400b6_1659344999.9830225.png" width="620"> \n\n**Input used in demonstration:**\n[[1,0,1,0,0,0,0], [1,1,1,1,1,0,0],[1,1,1,1,1,0,1],[0,0,1,1,1,1,0], [1,1,0,0,1,1,0],[0,0,0,0,1,1,0],[1,1,0,1,0,1,1]]\n\n**Approach I - Recursion** *(TLE)*\n```\nclass Solution {\npublic:\n    int solve(vector<vector<int>> &matrix, int m, int n, int i, int j){\n        if(i<0 or i>=m or j<0 or j>=n or matrix[i][j] == 0){\n            return 0;\n        }\n \n        int right = solve(matrix, m,n,i,j+1);\n        int bottom = solve(matrix, m, n, i+1, j);\n        int bottom_right = solve(matrix,m,n, i+1,j+1);\n\n        return 1 + min({right, bottom, bottom_right}); \n    }\n    \n    \n    int countSquares(vector<vector<int>>& matrix) {\n        int m = matrix.size();\n        int n = matrix[0].size();\n        int ans = 0;\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                if(matrix[i][j] == 1){\n                    ans += solve(matrix,m,n,i,j);\n                }\n            }\n        } \n        return ans;\n    }\n};\n```\n\n**Approach II - Memoization(Top-Down)**\n```\nclass Solution {\npublic:\n    int solve(vector<vector<int>> &matrix, int m, int n, int i, int j, vector<vector<int>> &dp){\n        if(i<0 or i>=m or j<0 or j>=n or matrix[i][j] == 0){\n            return 0;\n        }\n        if(dp[i][j] != -1) return dp[i][j];\n        int right = solve(matrix, m,n,i,j+1,dp);\n        int bottom = solve(matrix, m, n, i+1, j, dp);\n        int bottom_right = solve(matrix,m,n, i+1,j+1, dp);\n\n        return dp[i][j] =  1 + min({right, bottom, bottom_right}); \n    }\n    \n    int countSquares(vector<vector<int>>& matrix) {\n        int m = matrix.size();\n        int n = matrix[0].size();\n        vector<vector<int>> dp(m+1, vector<int>(n+1,-1));\n        int ans = 0;\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                if(matrix[i][j] == 1){\n                    ans += solve(matrix,m,n,i,j, dp);\n                }\n            }\n        }    \n        return ans;\n    }\n};\n```\n\n**Approach III - Tabulation(Bottom-Up)**\n```\nclass Solution {\npublic:\n\t  int countSquares(vector<vector<int>>& matrix) {\n        int m = matrix.size(), n = matrix[0].size(),  ans = 0;\n        for(int i=0;i<m;i++){\n            for(int j=0;j<n;j++){\n                if(i>0 and j>0 and matrix[i][j]>0)\n                    matrix[i][j] = 1+min(matrix[i-1][j-1], min(matrix[i-1][j], matrix[i][j-1]));\n                ans += matrix[i][j];\n            }\n        }\n        return ans;\n    }\n};\n```\n\nSome variations of this question could be return the max square submatrix or return the area of the maximum square submatrix.
['Dynamic Programming', 'Recursion', 'Memoization', 'C', 'C++']