Tìm ma trận con với tổng cho trước trong C++

Trong bài toán này, chúng ta được cho một ma trận 2D kích thước N*N và hai biến sum và size. Nhiệm vụ của chúng ta là tìm một ma trận con với tổng cho trước.

Ta cần tìm ma trận con kích thước size*size với tổng các phần tử bằng sum.

Hãy xem ví dụ sau để hiểu bài toán:

Input : mat[][] = {    {1, 5, 7, 9}    {2, 4, 6, 8}    {1, 2, 5, 6}    {3, 6, 9, 3} } sum = 22 Size = 2 Output : YES

Giải thích −

Ma trận con kích thước k với tổng 22 là {5, 7} {4, 6}

Phương pháp giải

Một giải pháp đơn giản là tạo tất cả ma trận con kích thước size*size có thể, tìm tổng và so sánh với tổng cho trước. Trả về nếu bằng nhau.

Một phương pháp khác sử dụng thuật toán quy hoạch động. Trong phương pháp này, ta tạo mảng DP lưu tổng đến chỉ số hiện tại, tức là DP[i][j] lưu tổng tất cả phần tử từ hàng 0 đến i và cột 0 đến j.

Sử dụng mảng DP này, ta tính tổng giữa hai chỉ số bắt đầu và kết thúc bằng công thức:

$$\mathrm{sum((i_s,j_s)to(i_e,j_e))\:=\:DP[i_s][i_s]\:+\:DP[i_e][i_e]\:-\:DP[i_s][i_e]\:-\:DP[i_e][i_s]}$$

Thuật toán

Bước 1 − Tạo ma trận DP kích thước (n+1)*(n+1).

Bước 2 − Với mỗi phần tử ma trận, tìm tổng đến chỉ số hiện tại.

Bước 3 − Với tất cả chỉ số từ 0 đến n, tìm tổng ma trận con kích thước size*size. Sử dụng công thức và lưu vào currSum.

Bước 4 − Nếu currSum == sum, trả về true.

Bước 5 − Trả về false.

Ví dụ

Chương trình minh họa cho giải pháp

#include <iostream> using namespace std; #define N 4 bool findSubMatWithSum(int size, int sum, int mat[N][N]){    int DP[N + 1][N + 1];    for (int i = 0; i < N; i++)    for (int j = 0; j < N; j++)    DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];    int currSum = 0;    for (int i = 0; i < N; i++)    for (int j = 0; j < N; j++) {       currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];       if (currSum == sum)       return true;    }    return false; } int main(){    int mat[N][N] = { { 1, 5, 7, 9 },    { 2, 4, 6, 8 },    { 1, 2, 5, 6 },    { 3, 6, 9, 3 } };    int size = 2;    int sum = 22;    if (findSubMatWithSum(size, sum, mat)) cout<<"Sub-Matrix of given size having the given sum is possible!";    else      cout<<"Sub-Matrix of given size having the given sum is not possible!"; }

Kết quả

Sub-Matrix of given size having the given sum is possible!