Standard Bar Dynamic Programming · DP on Squares O(m*n) · O(n)
A stadium groundskeeper maps a grass grid where 1 marks healthy turf and 0 marks worn patches. Maintenance orders are sized in square sections, and any all-healthy square — of any size, anywhere — can be turfed in one work order. The scheduler counts every all-ones square block in the grid to size the season's workload.
Input: An m x n binary matrix matrix of 0s and 1s.
Output: Return the number of square submatrices (of all sizes) consisting entirely of 1s.
1 <= m, n <= 300matrix[i][j] is 0 or 1Input: {"matrix":[[0,1,1,1],[1,1,1,1],[0,1,1,1]]}
Output: 15
Ten 1x1 squares, four 2x2 squares, and one 3x3 square — 15 total.
Input: {"matrix":[[1,0,1],[1,1,0],[1,1,0]]}
Output: 7
Five 1x1 squares plus two 2x2 squares.