Python commented code O(MN)
\nclass Solution:\n    def countSquares(self, A: List[List[int]]) -> int:\n        # Stores final squares count\n        countSquares = 0\n        \n        # d
```\nclass Solution:\n    def countSquares(self, A: List[List[int]]) -> int:\n        # Stores final squares count\n        countSquares = 0\n        \n        # dp[i][j] represents how many squares can be created if A[i][j]th element is used\n        # We will always consider using A[i][j]th element in the right corner when building a square\n        dp = [[0 for i in A[0]] for j in range(len(A))]\n        \n        for i in range(len(A)):\n            for j in range(len(A[0])):\n                # Checking if A[i][j]th element can acutally be used to create a square\n                # which will only happen if the element is 1 and there are adjacent elements\n                if A[i][j] and i > 0 and j > 0:\n                    # Considering A[i][j]th element to be on the right corner the number of squares \n                    # that can be created depends on adjacent 3 elements square count in dp\n                    # Consider below cases\n                    # ......\n                    # ..1,1\n                    # ..1,x    x depend on left, left-top, top if they are able to make square by staying on the right corner \n                    # .....    then joining x will also be able to make square by staying in the right corner. \n                    #          So what will be the number of square that x can make depends \n                    #          on how long square or how many squares \n                    #          that left, left-top, top element can make so we need to take the minimum of the 3\n                    #\n                    dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1\n                else:\n                    dp[i][j] = A[i][j]\n                \n                # Add the count to total count\n                countSquares += dp[i][j]\n        \n        return countSquares\n```
['Dynamic Programming', 'Python']