536. 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.

Constraints - `1 ≤ m ≤ 300` - `1 ≤ n ≤ 300` - every value is `0` or `1`