1277. 统计全为 1 的正方形子矩阵

解法一：动态规划

考虑 N 维子矩阵时，dp[N][i][j] 表示以元素 (i,j) 为左上角，边长为 N 的子矩阵内部是否全为1。
考察满足条件的 N 维矩阵时，不需要考察每一个元素，只需要考察相邻的4个满足条件的 N-1 维矩阵即可，动规方程方程如下：

class Solution {
    public int countSquares(int[][] matrix) {
        final int row = matrix.length;
        final int col = matrix[0].length;
        int ans = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] > 0) {
                    ++ans;
                }
            }
        }
        for (int k = 1; k < Math.min(row, col); ++k) {
            for (int i = 0; i < row - k; ++i) {
                for (int j = 0; j < col - k; ++j) {
                    matrix[i][j] = matrix[i][j] & matrix[i + 1][j] & matrix[i][j + 1] & matrix[i + 1][j + 1];
                    if (matrix[i][j] > 0) {
                        ++ans;
                    }
                }
            }
        }
        return ans;
    }
}

解法二：动态规划

参考官方题解：https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/solution/

class Solution {
    public int countSquares(int[][] matrix) {
        final int row = matrix.length;
        final int col = matrix[0].length;
        int[][] dp = new int[row][col];
        int ans = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (matrix[i][j] == 0) {
                    dp[i][j] = 0;
                } else if ((i == 0) || (j == 0)) {
                    dp[i][j] = matrix[i][j];
                } else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                ans += dp[i][j];
            }
        }
        return ans;
    }
}