分区2D阵列的索引以最小化子矩阵的总和

Question

给定 $ n \ times n $ matrix $ m $ ，和指数 $ [{1,2,3,4，...，n}] $ 分为多个间隔： $ [1， x_1]，[x_1，x_2]，... [x_k，n] $ ，其进一步提取了沿 $ m $ 的多个方形子矩阵'对角线 - $ m [1 ... x_1,1 ... x_1]，m [x_1 ... x_2，x_1 ... x_2]，... m [ x_k ... n，x_k ... n] $ 。

假设 $ sum（矩阵）$ 是矩阵中的所有元素的总和。如何设计一个算法来查找最佳分区，最小化 $ sum（m [1 ... x_1,1 ... x_1]）+ sum（m [x_1 ... x_2，x_1 ... x_2]）+ ... + sum（m [x_k ... n，x_k ... n]）$

要显示，找出一个分区，可最大限度地减少表中所有阴影元素的总和

Answer 1

首先，我们注意到，使用 $ \ mathcal {o}（n ^ 2）$ 预兆，我们可以在其中存储'前缀sum'，我们可以找到<一个href=“https://www.geeksforgeeks.org/submatrix-sum-qure/ies/”rel=“nofollow noreferrer”>给定的方形子流程中的所有元素的总和 $ \ mathcal {o}（1）$ 时间。

现在，让 $ dp [i] $ 是最佳答案，如果输入矩阵只有第一个 $ i $ 行和第一个 $ i $ 列。我们正在寻找的最终答案是 $ dp [n] $ 。

基本情况是 $ dp [0]= 0 $ 。

要计算 $ dp [i] $ ，我们遍历所有 $ j $ 这样的< Span Class=“Math-Container”> $ 1 \ Le J \ Leq i $ ，我们将分区中的最后一个间隔视为 $ [j，i] $ 。对于一个固定的 $ j $ ，最小和将是 $ dp [j-1] + sum（m [j \ ldots i] [j \ ldots i]）$ 。这导致等式

$$ dp [i]=min_ {1 \ leq j \ leq i}（dp [j-1] + sum（m [j \ ldots i] [J \ ldots i]））$$

所以， $ dp [i] $ 可以在 $ \ mathcal {o}（n）$ < / span>时间，整个问题需要 $ \ mathcal {o}（n ^ 2）$ 时间和空间。