Почему это работает
- Квадрат k × k из единиц с углом в (r, c) содержит квадраты (k - 1) × (k - 1), которые кончаются сверху, слева и по диагонали. Поэтому он есть ровно тогда, когда все три клетки дают хотя бы k - 1: dp — это 1 + наименьшая из них.
- Наименьшая и ограничивает: в (2, 3) слева 3, по диагонали 2, но сверху 1 — ноль в (0, 3) ломает там любой квадрат побольше.
- По строкам все три клетки, которые читает клетка, заполнены раньше неё, а side хранит наибольшее значение, поэтому в конце площадь — side × side.
Сложность
Время O(m × n): каждая клетка один раз читает трёх соседей. Память O(m × n) на таблицу; клетка читает только свою строку и строку над ней, так что хватит двух строк.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗