1277. Count Square Submatrices with All Ones

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1

for border needs special handling, (first row, first col)

count add each dp[][] result

這三個位置的 以 i j 為右下角的正方 的  min（之前三個位置的結果） +1 (右下的本身） ⇒ 決定了 dp[i][j] 能多大

**dp[i][j]  = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1**


/*
how to make
1,1
1,1

?
 --------------------
|(i-1,j-1) | (i-1, j)|
|--------------------|
|(i, j-1)  | (i,j)   |
 --------------------

i, j => 3 cases

(1)

1,1 add one row  (i-1, j)
  
or 
(2)

1    add one col  (i, j-1)
1.  

(3)
1.  add one row and add one col
    (i-1, j-1)
    
so 
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) +1   

+1 is self is square
    
*/

time: O(mn)

space: O(mn)

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n]; // matrix is 0,0 based
        int count = 0;
        
        // 處理 first col
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 1) { 
                dp[i][0] = 1;
                count++;
            }
        }
        // 處理 first row
        for (int i = 1; i < n; i++) {
            if (matrix[0][i] == 1) {
                dp[0][i] = 1;
                count++;
            }
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 1) {
                    dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
                    count += dp[i][j];
                }
            }
        }
        return count;
    }
}j

easier version

把結果更新到本身, in-place

time: O(mn)

space: O(1)

class Solution {
    public int countSquares(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1 && i > 0 && j > 0) { // 只計算 matrix[i][j] == 1 && i, j > 0 的部分
                    // 那為何還要start from i = 0, j = 0? 
                    // 因為外面的 count 會加 i = 0, j = 0 的 1 的正方形數量 (面積為1的, 第一row & 第一col 的部分)
                    // 這樣就不用特別在外面處理第一row和第一col
                    matrix[i][j] = Math.min(matrix[i-1][j], Math.min(matrix[i][j-1], matrix[i-1][j-1])) + 1;
                } // 把結果累積到 matrix[i][j], 前提 (matrix[i][j] == 1) {
                count += matrix[i][j];
            }
        }
        return count;
    }
}