Easy Dynamic Programming Approach✅✅
Intuition\nThe goal is to count the number of square submatrices filled with 1s in a given binary matrix. Observing that any square of size greater than 1 can b
# Intuition\nThe goal is to count the number of square submatrices filled with 1s in a given binary matrix. Observing that any square of size greater than 1 can be built upon smaller squares, we can use a dynamic programming approach to solve this problem.\n\n# Approach\n1. Use a 2D `dp` array where `dp[i][j]` represents the size of the largest square submatrix ending at cell `(i, j)`.\n2. If `matrix[i][j] == 1`, set `dp[i][j]` as:\n   - `1` if it\'s on the top row or leftmost column (it can only be a 1x1 square).\n   - Otherwise, `dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])`.\n3. Sum all values in `dp` to get the count of all square submatrices.\n\n# Complexity\n- **Time complexity:** \\(O(n \\times m)\\), where \\(n\\) and \\(m\\) are the number of rows and columns in the matrix, since each cell is processed once.\n- **Space complexity:** \\(O(n \\times m)\\), for the `dp` array storing subproblem results.\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int countSquares(vector<vector<int>>& matrix) {\n        int n = matrix.size();\n        int m = matrix[0].size();\n        vector<vector<int>> dp(n, vector<int>(m, 0));\n\n        // Fill dp array based on conditions\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                if (matrix[i][j] == 1) {\n                    if (i == 0 || j == 0) {\n                        dp[i][j] = 1;  // Border cells can only form 1x1 squares\n                    } else {\n                        dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});\n                    }\n                }\n            }\n        }\n\n        // Sum up all values in dp array to get total count of square submatrices\n        int ans = 0;\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < m; j++) {\n                ans += dp[i][j];\n            }\n        }\n        return ans;\n    }\n};\n
['Dynamic Programming', 'Prefix Sum', 'C++']