使用 Python 计算所有子矩阵的程序
假设我们有mxn二进制矩阵，我们必须找出有多少个子矩阵都是1。
所以，如果输入是这样的
那么输出将是13，因为有6个(1x1)矩阵、3个(2,1)矩阵、2个(1x2)矩阵、1个(3x1)矩阵和1个(4x4)矩阵。
为了解决这个问题，我们将按照以下步骤操作-
m:=矩阵的行数
n:=矩阵的列数
dp:=相同大小的零矩阵mxn
对于0到m-1范围内的i，请执行
如果i与0和矩阵[i,j]相同，则
否则当matrix[i][j]非零时，则
dp[i,j]:=1
dp[i,j]:=dp[i-1,j]+1
对于0到n-1范围内的j，执行
总计：=0
对于0到m-1范围内的i，请执行
对于j+1到n范围内的k，做
总计:=总计+dp[i,j]到dp[i,k]的最小值
对于0到n-1范围内的j，执行
总回报
让我们看看以下实现以获得更好的理解-
示例
def solve(matrix):
m = len(matrix)
n = len(matrix[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and matrix[i][j]:
dp[i][j] = 1
elif matrix[i][j]:
dp[i][j] = dp[i-1][j] + 1
total = 0
for i in range(m):
for j in range(n):
for k in range(j+1, n+1):
total += min(dp[i][j:k])
return total
matrix = [[1,0,1],[0,1,1],[0,1,1]]
print(solve(matrix))输入
[4,6,7,8], 11输出结果
13