Time complexity: O(mn). Space complexity: O(1)
Let (x, y) be the bottom-right corner of multiple squares of different sizes.\n Let matrix[x][y] be the number of squares whose the bottom-right corner is (x, y
* Let `(x, y)` be the bottom-right corner of multiple squares of different sizes.\n* Let `matrix[x][y]` be the number of squares whose the bottom-right corner is `(x, y)`. `matrix[x][y]` is also the width of the biggest square whose the bottom-right corner be `(x, y)`.\n\nNow comes the DP part:\n\n* We skip `(x, y)` whose original `matrix[x][y]` value is `0` because they cannot be the bottom-right corner of any squares.\n* Consider `matrix[x][y]` as the width of the biggest square whose the bottom-right corner be `(x, y)`.\n\t* `matrix[x][y] = n` if and only if `matrix[x - 1][y] = matrix[x][y - 1] = matrix[x - 1][y - 1] = n - 1`.\n\t* What will happen if `matrix[x - 1][y]`, `matrix[x][y - 1]` and `matrix[x - 1][y - 1]` does not share the same value? Let\'s look at the following illustration of a matrix in the mid of computation:\n\n| 1 | 1 | 1 | 0 |\n| 1 | 2 | 2 | 0 |\n| 1 | 2 | **3** | **1** |\n| 0 | 0 | **1** | **?** |\n\nwhere `matrix[x - 1][y] = matrix[x][y - 1] = 1` and `matrix[x - 1][y - 1] = 3`. It turns out `matrix[x][y] = 2`.\n\nOr, to be more generic:\n\n`matrix[x][y] = min(matrix[x - 1][y], matrix[x][y - 1], matrix[x - 1][y - 1]) + 1`\n\n```python\nclass Solution(object):\n    def countSquares(self, matrix):\n        """\n        :type matrix: List[List[int]]\n        :rtype: int\n        """\n        \n        count = sum(matrix[0])\n        for i in range(1, len(matrix)):\n            count += matrix[i][0]\n        \n        for i in range(1, len(matrix)):\n            for j in range(1, len(matrix[i])):\n                if matrix[i][j] == 0:\n                    continue\n                matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]) + 1\n                count += matrix[i][j]\n                \n        return count\n```
['Dynamic Programming', 'Python']