Там все числа от 1 и по прядку

Ну бред же) такие тесты давать

Там разве сказано явно про это в условии?

ага, похожа. только дпшечка не с самим ответом, а просто помогает за O(1) получить количество единиц в квадрате, но проверить их все нужно ручками.

В каждой клетке как раз количество квадратов, которое нужно добавить.

т.е. у тебя каждая клетка — количество каких квадратов? которые правым нижним углом заканчиваются в этой клетке?

O(N) по памяти и O(N) по доступам это лучшее?

https://leetcode.com/problems/count-square-submatrices-with-all-ones/discuss/643527/C-simple-O(mn)-DP-solution

Любопытно, да. https://gist.github.com/vitkarpov/95744ed3ebf82a38682e8497e488cba6 Я делал на основе вот этой идеи: количество единиц между двумя точками (когда проверяем квадраты) можно подсчитать если вычесть зелёные и красные области и прибавить их пересечение (потому что дважды вычли). Таким образом за O(1) можно спросить количество единиц в квадрате, а потом просто пробежаться надо по всем квадратам — это O(N^3)

Выкинул лишнее из прошлого решения по квадрату и поправил

Это вроде в посказках было

Любопытно, да. https://gist.github.com/vitkarpov/95744ed3ebf82a38682e8497e488cba6 Я делал на основе вот этой идеи: количество единиц между двумя точками (когда проверяем квадраты) можно подсчитать если вычесть зелёные и красные области и прибавить их пересечение (потому что дважды вычли). Таким образом за O(1) можно спросить количество единиц в квадрате, а потом просто пробежаться надо по всем квадратам — это O(N^3)

Это вроде в посказках было

Общее количество единиц в квадрате, т.е. площадь?

Мне нравится. Лучше, чем у меня вышло 👍

типа того. у тебя есть площадь квадрата и если единиц меньше, значит где-то там не хватало 1

Любопытно, да. https://gist.github.com/vitkarpov/95744ed3ebf82a38682e8497e488cba6 Я делал на основе вот этой идеи: количество единиц между двумя точками (когда проверяем квадраты) можно подсчитать если вычесть зелёные и красные области и прибавить их пересечение (потому что дважды вычли). Таким образом за O(1) можно спросить количество единиц в квадрате, а потом просто пробежаться надо по всем квадратам — это O(N^3)

Под влиянием задачи про магический словарь подумал, что такой подход можно использовать для подсчета, например, количества не только полных квадратов, но и квадратов, которые можно получить заменой 1,2,3 и т.д. нулей на единицу)

Сегодняшняя очень похожа

я, наверное, не очень понял о чем речь.

Сегодняшня задачка очень похожа с задачкой про острова

Сегодняшня задачка очень похожа с задачкой про острова

Читая CLRS, я только сейчас понял что задачка про buy and sell stocks сводится к задаче про max subarray sum и решается тем самым Кейденом. Только в задаче про стоки у него получается ещё и логическое объяснение.

В том, что отрицательной прибыли не может быть?

Это из книги CLRS если что 🙂