サブマトリックスの合計を最小限に抑えるために2Dアレイのインデックスを分割する

Question

$ n \ times n $ matrix $ m $ 、およびインデックス $ [{1,2,3,4、...、n}] $ はいくつかの間隔に分けられます。 $ [1、 X_1]、[X_1、X_2]、... [X_K、N] $ 。 $ m $ に沿っていくつかの2乗サブ行列を抽出します。 'SPAN CLASS="Math-Contains"> $ m [1 ... x_1,1 ... x_1]、m [x_1 ... x_2、x_1 ... x_2]、... m [ X_K ... n、x_k ... n] $ 。

$ sum（matrix）$ は、行列内のすべての要素の合計です。 $ sum（m [1 ... x_1,1 ... x_1]）を最小限に抑える最適なパーティションを見つけるためのアルゴリズムを設計する方法（m [x_1 ... x_2、x_1 ... x_2]）+ ... + ... + sum（m [x_k ... n、x_k ... n]）$

視覚化するには、以下の表のすべての網掛けの要素の合計を最小限に抑えるパーティションを調べます。

Answer 1

最初に $ \ mathcal {o}（n ^ 2）$ 事前計算、「プレフィックス合計」を保存する前に注意してください。 href="https://www.geeksforgeeks.org/submatrix-sum-queries/" rel="nofollow noreferrer"> $ \ mathcal {O}（1）$ 時間

今、 $ dp [i] $ を最適な回答で、入力行列が最初の $のみにした場合i $ 行と最初の $ i $ 列。探している最後の答えは $ dp [n] $ です。

基本ケースは $ dp [0]= 0 $ です。

compute $ dp [i] $ を除く、 $ j $ を繰り返します。 SPAN CLASS="math-container"> $ 1 \ lej \ 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]））$$

so、 $ dp [i] $ は $ \ mathcal {O}（n）$ < / SPAN>時間、そして全体の問題は $ \ mathcal {o}（n ^ 2）$ 時間と空間を受けます。