1504. Count Submatrices With All Ones

DP

O(m*n*worst(m)) = O(m^2n)

如果今天只是1d array...

[1,1,1,1]

那是不是就是 1 + 2 + 3 +4 = 10, 10 種 matrices

所以在某 row 上, 持續看左邊去增長, 如果中間有 0 的, 那就是 0 （斷掉了

row 看左邊完了

那在看上面...所以再跑一個 for 看上面 , 看每個元素值最小多少, 代表可以湊成更多的 matrices, 一樣, 如果中間有 0 就斷掉了

ex:

1 → 0

0 → 0

1 → 1. 中間斷掉了 所以只能算一個

其他向上看的 case

1

1

1 → 代表有三個！1+1+1

2

1

1 → 還是 3 個

class Solution {
   public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    continue;
                }
                // cal left
                mat[i][j] = (j == 0 ? 0 : mat[i][j-1]) + 1;
                count += mat[i][j];
                
                // cal up
                int min = mat[i][j];
                for (int k = i-1; k >= 0; k--) {
                    min = Math.min(min, mat[k][j]);
                    count += min;
                }
            }
        }
        return count;
    }
}

/*
O(m*n*worst(m))
*/

python

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:

        count = 0
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                if mat[i][j] == 0:
                    continue
                    
                mat[i][j] = (0 if (j == 0) else mat[i][j-1]) + 1
                count += mat[i][j]
                
                min_val = mat[i][j]
                for k in range(i-1, -1, -1):
                    
                    min_val = min(min_val, mat[k][j])
                    count += min_val
        return count