1277. Count Square Submatrices with All Ones

Link

Solution

dp[i][j] denotes the square size which right bottom is A[i][j]

square size is equal to square count.

for dp[i][j], the maximun size it can get is base on it's neightbots, dp[i-1][j], dp[i][j-1], dp[i-1][j-1], it can only extend the case with minum size among them

for example

1 1 1 1 0 1 1 1 1(2)1 < - 1 0 1 1 1 1 < -2 3

  public int countSquares(int[][] A) {
        int m = A.length;
        int n = A[0].length;
        int[][] dp = new int[m][n]; // dp[i][j] is the count of square 
                                    // which bottom-right is A[i][j]
        int ret = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(A[i][j] == 1){
                    if(i == 0 || j == 0){
                         dp[i][j] = A[i][j];
                    }
                    else{
                        dp[i][j] = Math.min(dp[i-1][j], 
                                            Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                    }
                    ret += dp[i][j];
                }
            }
        }
        return ret;
    }