Simple DP using Java,C(O(N*M))
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n1. DP Table Definition:
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. **DP Table Definition:**\n    - We define a DP table such that dp[i][j] represents the size of the largest square submatrix (filled with 1s) whose bottom-right corner is at the position (i-1, j-1) in the original matrix.\n2. **Recurrence Relation:**\n    - For each cell (i, j) in the input matrix:\n        - If matrix[i][j] is 1, it can contribute to a square submatrix. We calculate the size of the largest square submatrix that can end at (i, j) using the values from the DP table of the surrounding cells:\n       **dp[i+1][j+1]=1 + min( dp[ i ][ j ] , dp[ i+1 ][ j ] , dp[ i ][ j+1 ] )**\n        - The i,j corresponds to:\n            - dp[i][j] (top-left diagonal)\n            - dp[i][j+1] (above)\n            - dp[i+1][j] (left)\n        - This works because the largest square that can be formed at (i, j) depends on the smallest square that can be formed at the adjacent top, left, and top-left diagonal positions. Adding 1 to this minimum value indicates that a new square can be formed.\n3. **Count the Squares:**\n    - We maintain a counter (squares) that accumulates the sizes of the squares computed in dp[i+1][j+1]. This means every time we compute dp[i+1][j+1], we are adding the count of squares of all sizes (from 1x1 to the size represented by dp[i+1][j+1]).\n# Complexity\n- Time complexity:O(N*M)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N*M)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int m = matrix.length, n = matrix[0].length;\n        int[][] dp = new int[m + 1][n + 1];\n        int squares = 0;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (matrix[i][j] == 1)\n                    dp[i + 1][j + 1] = 1 + Math.min(dp[i][j], Math.min(dp[i + 1][j], dp[i][j + 1]));\n                squares += dp[i + 1][j + 1];\n            }\n        }\n        return squares;\n    }\n}\n```\n```C []\nint countSquares(int** matrix, int matrixSize, int* matrixColSize) {\n    int m = matrixSize;\n    int n = *matrixColSize;\n    int** dp = (int**)malloc((m + 1) * sizeof(int*));\n    for (int i = 0; i <= m; i++) {\n        dp[i] = (int*)calloc((n + 1), sizeof(int));\n    }\n    int squares = 0;\n    for (int i = 0; i < m; i++) {\n        for (int j = 0; j < n; j++) {\n            if (matrix[i][j] == 1) {\n                dp[i + 1][j + 1] = 1 + (dp[i][j] < dp[i + 1][j] ? (dp[i][j] < dp[i][j + 1] ? dp[i][j] : dp[i][j + 1]) : (dp[i + 1][j] < dp[i][j + 1] ? dp[i + 1][j] : dp[i][j + 1]));\n                squares += dp[i + 1][j + 1];\n            } else {\n                dp[i + 1][j + 1] = 0;\n            }\n        }\n    }\n    return squares;\n}\n```
['Java']