1277. Count Square Submatrices with All Ones

Define the subproblem dp[i][j] = the side length of the largest all-1 square whose bottom-right corner is (i, j). This value equals the number of distinct squares ending at that corner (one of each side from 1 up to dp[i][j]). The recurrence relation is dp[i][j] = 0 if matrix[i][j] == 0, else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) — a square of side s ending here requires that s-1 squares exist above, left, and on the diagonal. Base case: cells in row 0 or column 0 with matrix[i][j] == 1 contribute dp[i][j] = 1. Sum dp over the whole grid for the answer. You can update the matrix in place to save memory, or roll two rows. O(m * n) time, O(m * n) or O(min(m, n)) space.