# 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 個

```java
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

```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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/specail-square-dp/1504.-count-submatrices-with-all-ones.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.