[Java] DP O(mn), Straightforward, Explained
Find recursive relation\nLet dp be an 2d array. Let dp[i][j] represent the max side length of the square that\n1. has all ones in it, AND\n1. has its bottom-rig
## Find recursive relation\nLet `dp` be an 2d array. Let `dp[i][j]` represent the **max side length** of the square that\n1. has all ones in it, AND\n1. has its **bottom-right** (we will see why bottom-right later) cornor positioned at `(i, j)`\n\nFor example, the `dp` array for matrix\n```\n111\n011\n111\n```\nwill be\n```\n111\n012\n112\n```\nWe found that the total number of all-one squres for the matrix is equal to the sum of the `dp` array. This is because for a given position `(i, j)`, if square `[(i-2, j-2), (i, j)]` is an all-one square, then `[(i-1, j-1), (i, j)]` is also an all-one square, same for square `[(i, j), (i, j)]`.\n\nIn order to achive this way of representation, we need the following recursive relation:\n\n`dp[i][j]` = \n* `0`, if `matrix[i][j] = 0`\n* `matrix[i][j]`, if `i=0` or `j = 0` (if first row or first column)\n* `min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`, otherwise\n\nHere we see, in order to find `dp[i][j]`, we might need `dp[i-1][j]`, `dp[i][j-1]`, and `dp[i-1][j-1]`. This is because we let `dp[i][j]` represent the max side length of square that has its **bottom-right** cornor positioned at `(i, j)`. If we choose to let `dp[i][j]` represent the max side length of square that has its **top-left** cornor positioned at `(i, j)`, we will need `dp[i+1][j]`, `dp[i][j+1]`, and `dp[i+1][j+1]` instead to find `dp[i][j]`, and this will work but just make the double for-loop run reversely.\n\n\n## Implement code\nIn implementation, we do not need to actually store the entire `dp` array in memory, we can simply accumulate our temporary results into a single variable `count`:\n```\nclass Solution {\n    public int countSquares(int[][] matrix) {\n        int count = 0;\n        int numRow = matrix.length;\n        int numCol = matrix[0].length;\n        \n        for (int i=0; i<numRow; ++i) {\n            for (int j=0; j<numCol; ++j) {\n                if (i != 0 && j != 0 && matrix[i][j] != 0) {\n                    matrix[i][j] = Math.min(matrix[i-1][j], Math.min(matrix[i][j-1], matrix[i-1][j-1])) + 1;\n                };\n                count += matrix[i][j];\n            }\n        }\n        return count;\n    }\n}\n```\nNote since `Math.min()` only support comparision between two variables, we need extra ugly code for comparing `dp[i-1][j]`, `dp[i][j-1]`, and `dp[i-1][j-1]`.\n\n\n## Complexity Analysis\n- Time Complexity: `O(mn)` as we traversed the entire matrix once\n- Space Complexity: `O(1)` as we only kept a single variable\n
['Dynamic Programming', 'Java']