数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学在 C++ 中查找具有给定和的子矩阵
在这个问题中，我们给定一个大小为 N*N 的二维矩阵和两个变量 sum 和 size。我们的任务是查找具有给定和的子矩阵。
我们需要找到一个大小为 size*size 且元素和等于 sum 的子矩阵。
让我们来看一个例子来理解这个问题：
Input : mat[][] = {
{1, 5, 7, 9}
{2, 4, 6, 8}
{1, 2, 5, 6}
{3, 6, 9, 3}
}
sum = 22
Size = 2
Output : YES说明 −
The submatrix of size k with sum 22 is
{5, 7}
{4, 6}解决方案方法
解决这个问题的一个简单方法是创建所有可能的 size*size 大小的子数组，求和，然后将其与给定的 sum 值相等。如果两者相等则返回。
另一种方法是使用动态规划算法的概念。在这种方法中，我们将创建一个 DP 数组，该数组将存储直到当前索引值的总和，即 DP[i][j] 将存储从行索引 0 到 i 和列索引 0 到 j 的所有数组元素的总和。
使用这个 DP 数组，我们将使用以下公式计算任意两个起始索引和结束索引之间的总和：
$$\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]}$$
算法
步骤 1 − 创建一个大小为 (n+1)*(n+1) 的 DP 矩阵。
步骤 2 − 对于矩阵的每个元素，找到直到当前索引的总和。
步骤 3 − 对于从 0 到 n 的所有索引，找到 size*size 大小的子矩阵的总和。使用公式并将结果存储在 currSum 中。
步骤 4 − 如果 currSum == sum，则返回 true。
步骤 5 − 返回 false。
示例
程序演示了我们解决方案的工作原理
#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!";
}输出
Sub-Matrix of given size having the given sum is possible!
更新于： 2022年1月25日
1K+ 次浏览
广告