Python | DP
see the Successfully Accepted Submission\n\n# Code\npython3 []\nfrom typing import List\n\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) 
[see the Successfully Accepted Submission](https://leetcode.com/problems/count-square-submatrices-with-all-ones/submissions/1434829266/?envType=daily-question&envId=2024-10-27)\n\n# Code\n```python3 []\nfrom typing import List\n\nclass Solution:\n    def countSquares(self, matrix: List[List[int]]) -> int:\n        if not matrix or not matrix[0]:\n            return 0\n\n        m, n = len(matrix), len(matrix[0])\n        dp = [[0] * n for _ in range(m)]\n        total_squares = 0\n        \n        for i in range(m):\n            for j in range(n):\n                if matrix[i][j] == 1:\n                    if i == 0 or j == 0:\n                        dp[i][j] = 1  # On edges, a single \'1\' forms a 1x1 square\n                    else:\n                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n                    total_squares += dp[i][j]\n\n        return total_squares\n\n```\n\n\n# Approach\n\n### DP Matrix Definition:\n- Let `dp[i][j]` represent the size of the largest square submatrix with all ones that ends at cell \\((i, j)\\).\n- If `matrix[i][j]` is zero, then `dp[i][j]` should be zero because we can\'t form a square submatrix ending in a cell with a zero.\n\n### Transition Formula:\n- If `matrix[i][j]` is one, then:\n  \\[\n  dp[i][j] = \\min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1\n  \\]\n- This formula works because the size of the square ending at \\((i, j)\\) is limited by the smallest square ending to its left, top, or top-left diagonal cells.\n\n### Summing up Squares:\n- Each `dp[i][j]` represents the side length of the largest square ending at \\((i, j)\\).\n- The number of squares ending at \\((i, j)\\) is equal to `dp[i][j]` itself.\n- Accumulate all values in the `dp` matrix to get the total count of square submatrices.\n\n### Time Complexity:\n- The solution runs in \\(O(m \\times n)\\) time, where \\(m\\) and \\(n\\) are the dimensions of the matrix.\n\n### Space Complexity:\n- The solution uses \\(O(m \\times n)\\) space for the `dp` matrix, though we can optimize to \\(O(n)\\) by reusing rows.\n\n\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']