Giả sử chúng ta có một ma trận 2D được gọi là ma trận, chúng ta phải tìm tổng các phần tử bên trong hình chữ nhật được xác định bởi góc trên bên trái của nó bằng cách sử dụng (row1, col1) và góc dưới bên phải bằng cách sử dụng ( row2, col2).
Vì vậy, nếu ma trận giống như -
| 3 | 0 | 1 | 4 | 2 |
| 5 | 6 | 3 | 2 | 1 |
| 1 | 2 | 0 | 1 | 5 |
| 4 | 1 | 0 | 1 | 7 |
| 1 | 0 | 3 | 0 | 5 |
Hình chữ nhật trên với màu xanh lam được xác định bởi (2,1) và (4,3), hình này chứa tổng 8.
Vì vậy, nếu chúng ta thực hiện một số truy vấn như sumRegion (2, 1, 4, 3), sumRegion (1, 1, 2, 2), sumRegion (1, 2, 2, 4), chúng sẽ trả về 8, 11, 12 tương ứng.
Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -
-
Xác định ma trận được gọi là dp.
-
Khởi tạo tác vụ như sau
-
n:=số hàng. nếu n là 0, thì trả về,
-
m:=số cột
-
dp:=một ma trận khác có kích thước n x m
-
cho tôi trong phạm vi từ 0 đến n
-
cho j trong phạm vi từ 0 đến m
-
khi j - 1 <0, thì đặt dp [i, j] làm ma trận [i, j], nếu không thì đặt là (dp [i, j - 1] + ma trận [i, j])
-
-
-
cho tôi trong phạm vi từ 1 đến n
-
cho j trong phạm vi từ 0 đến m
-
tăng dp [i, j] lên dp [i - 1, j]
-
-
-
Đối với phương thức truy vấn, điều này sẽ lấy row1, col1, row2, col2
-
ret:=dp [row2, col2]
-
sub1:=0 khi row1 - 1 <0, nếu không nó sẽ là dp [row1 - 1, col2]
-
sub2:=0 khi col1 - 1 <0, nếu không nó sẽ là dp [row2, col1 - 1]
-
nếu row1 - 1 <0 hoặc col1 - 1 <0, thì
-
thêm:=0
-
-
nếu không thì thêm:=dp [row1 - 1, col1 - 1]
-
trả về ret - sub1 - sub2 + thêm
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
public:
vector < vector <int>> dp;
NumMatrix(vector<vector<int>>& matrix) {
int n = matrix.size();
if(!n) return;
int m = matrix[0].size();
dp = vector < vector <int>>(n, vector <int> (m));
for(int i = 0; i < n; i++){
for(int j = 0 ;j < m; j++){
dp[i][j] = j - 1 < 0 ? matrix[i][j] : dp[i][j - 1] + matrix[i][j];
}
}
for(int i = 1; i < n; i++){
for(int j = 0; j < m; j++){
dp[i][j] += dp[i - 1][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int ret = dp[row2][col2];
int sub1 = row1 - 1 < 0 ? 0 : dp[row1 - 1][col2];
int sub2 = col1 - 1 < 0 ? 0 : dp[row2][col1 - 1];
int add = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : dp[row1 - 1][col1 - 1];
return ret - sub1 - sub2 + add;
}
};
main(){
vector<vector<int>> mat = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
NumMatrix ob(mat);
cout << ob.sumRegion(2,1,4,3) << endl;
cout << ob.sumRegion(1,1,2,2) << endl;
cout << ob.sumRegion(1,2,2,4) << endl;
} Đầu vào
[[3,0,1,4,2], [5,6,3,2,1], [1,2,0,1,5], [4,1,0,1,7], [1,0,3,0,5]] sumRegion(2,1,4,3) sumRegion(1,1,2,2) sumRegion(1,2,2,4)
Đầu ra
8 11 12