Count the Squares of Ones
Count all square submatrices consisting entirely of 1s, of every size including single
cells.
1 1
1 1 -> 5 four single cells and one 2 by 2
## The same table, read differently
Problem 534 computes
dp[r][c] = the side of the largest all-ones square whose bottom-right corner is (r, c)
and takes the maximum. This problem takes the SUM.
The reason that works is worth spelling out. If the largest square ending at (r, c) has
side k, then squares of side 1, 2, ..., k all end there too, each nested inside the
next, and there are no others. So dp[r][c] is exactly the NUMBER of all-ones squares with
bottom-right corner (r, c).
Every square has exactly one bottom-right corner, so summing over all cells counts each square once. Same partition-by-anchor argument as problem 532's partition by last move.
## One table, two questions
max over cells -> the largest square (problem 534)
sum over cells -> how many squares (this problem)
This is the cheapest kind of generalisation to spot: the recurrence is unchanged and only the final reduction differs. It is worth asking, of any optimisation DP, whether the table already contains the count.
Note the asymmetry with problem 535: squares generalise from "largest" to "how many" for free, and rectangles do not, because the rectangle solution never builds a per-cell count.
## Boundaries
A 3 by 3 block of ones answers 14: nine single cells, four 2 by 2 squares, one 3 by 3. Checking that by hand is the fastest way to confirm the nesting argument.
An all-zero grid answers 0, and a single 1 answers 1.
1 0 1 / 0 1 0 / 1 0 1 answers 5: five isolated ones and nothing larger.
## Overflow
The count reaches roughly m n min(m, n), which at 300 by 300 is about 2.7 * 10^7. That
fits in 32 bits, but the running total is worth keeping in 64 to avoid thinking about it.
## Cost
Time O(m n). Space O(n) with two rows.