DP with figure explanation
\n\n----\n----\n## ## Explanation\n\n dp[i][j] represent edge length of the biggest square whose lower right corner element is matrix[i][j]. Also there are dp[i
![image](https://assets.leetcode.com/users/migeater/image_1575196646.png)\n\n----\n----\n## ## Explanation\n\n `dp[i][j]` represent edge length of the biggest square whose lower right corner element is `matrix[i][j]`. Also there are `dp[i][j]` squares whose lower right corner element are `matrix[i][j]`. The answer of count-square-submatrices-with-all-ones is sum of all `dp[i][j]`.\n\nAs Figure, **the square edge length** ( whose lower right corner element is `matrix[i][j]` ) is not greater than  `the minimum of three arrows + 1`. \n\nFortunately it can be equal to when `matrix[i][j]==1`. On this condition `dp[i][j]=the minimum of three arrows + 1`;\n\nAnd when `matrix[i][j]==0` , `dp[i][j]=0`.\n\nSo\n\n```py\nif matrix[i][j]==1 : \n    if i!=0 and j!=0: \n        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1\n    else: \n        dp[i][j] = 0 + 1\nelse:\n    dp[i][j] = 0\n```\n\nIn the 3rd line, each `dp[i][j]` is reused for 3 times.\nIf you think there are too many coincidences, please read next paragraph.\nNow we can write a top-down recursive algorithm:\n\n----\n\n### ### A top-down DP\n\ntime O(m*n), space O(m*n)\n\n```py\nclass Solution(object):\n    def countSquares(self, matrix):\n        m, n = len(matrix), len(matrix[0])\n\n        @cache # memorize\n        def dp(i,j):\n            if matrix[i][j]==1 : \n                if i!=0 and j!=0:\n                    return min(dp(i-1,j), dp(i,j-1), dp(i-1,j-1))+1\n                else:\n                    return 0+1\n            else:\n                return 0\n        \n        return sum(dp(i,j) for i in range(m) for j in range(n))\n```\n\nAfter wrtie this we know the call order of the dp function, then we can change it to bottom-up, make sure each dp(i,j) is calculated before dp(i,j+1) and dp(i+1,j) and dp(i+1,j+1). That\'s the classic iteration order: from left to right and from up to down.\n\n---\n\n### ### A bottom-up DP\n\ntime O(m*n), space O(m*n)\n\nHere in order to easily process border condition, use `dp[i+1][j+1]` save edge length of the biggest square whose lower right corner element is `matrix[i][j]`.\n\n```py\nclass Solution(object):\n    def countSquares(self, matrix):\n        m, n = len(matrix), len(matrix[0])\n        dp = [[0] * (n+1) for _ in range(m+1)] # new int[m+1][n+1];\n        ans = 0\n        for i in range(m):\n            for j in range(n):\n                if matrix[i][j]:\n                    dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1\n                    ans += dp[i+1][j+1]\n        return ans\n```\n\n----\n----\n\n## ## P.S. \n\nThe same problem: https://leetcode.com/problems/maximal-square/\nsimilar: https://leetcode.com/problems/minimum-path-sum/\nextend: https://leetcode.com/problems/count-fertile-pyramids-in-a-land\nharder(still can use one dp): https://codeforces.com/contest/1393/problem/D\n\nMore about top-down and bottom-up \nhttps://leetcode.com/explore/learn/card/recursion-i/\nhttps://leetcode.com/explore/learn/card/recursion-ii/\n
['Dynamic Programming', 'Python3']