# 1. Tóm tắt đề bài

Cho một bảng số $a$ có kích thước $n \times m$, hãy tìm số lượng bảng con có tổng giá trị bằng $target$.

##### Giới hạn
- $1 \le n, m \le 100$.
- $-1000 \le a_{i, j} \le 1000$.
- $-10^8 \le target \le 10^8$.

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(m^2 \times n)$**

Cố định hai cột và duyệt qua từng hàng, đưa về bài toán đến số đoạn con $1$ chiều có tổng bằng $target$.

# 3. Lời giải chi tiết

Ta cố định hai cột $c1$ và $c2$ của hình chữ nhật và cần đếm số bảng con có góc trái trên là $(r1, c1)$ và góc phải dưới là $(r2, c2)$ có tổng bằng $target$, hay đếm số cặp $(r1, r2)$ thỏa mãn. Gọi $f[i]$ là tổng của hàng $i$ trong đoạn $[c1..c2]$. Bài toán đã được đưa về trên mảng một chiều như sau:

Cho mảng $f$, hãy đếm số đoạn con của mảng sao cho tổng của nó bằng $target$.

Bài toán trên dễ dàng giải được trong độ phức tạp $O(n)$ bằng cách duy trì mảng cộng dồn và lưu trữ các giá trị cộng dồn trước đó vào một hash map. (Tìm đọc ở [đây](https://www.geeksforgeeks.org/find-subarray-with-given-sum-in-array-of-integers/))

Tổng quát lại, việc cố định hai cột $c1, c2$ mất $O(m^2)$ và giải bài toán trên mảng $1$ chiều mất $O(n)$, tổng quát ta có được một thuật toán chạy trong $O(m^2 \times n)$.
### Độ phức tạp thuật toán

Thời gian: $O(m^2 \times n)$

Bộ nhớ mở rộng: $O(m \times n)$

# 4. Kết luận & Gợi ý mở rộng
- [Kadane Algorithm GFG](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/)
- [Find Maximum Submatrix](https://www.geeksforgeeks.org/maximum-sum-submatrix/)