Partition des indices de la matrice 2D pour minimiser la somme des sous-matrices

Question

donné une $ n \ fois n $ matrice $ m $ et les indices $ [{1,2,3,4, ..., n}] $ sont divisés en plusieurs intervalles: $ [1, x_1], [x_1, x_2], ... [x_k, n] $ , qui extrait encore plusieurs sous-matrices carrées le long de la $ m $ Diagonale - $ m [1 ... x_1,1 ... x_1], m [x_1 ... x_2, x_1 ... x_2], ... m [ x_k ... n, x_k ... n] $ .

Supposons $ Somme (matrice) $ est la somme de tous les éléments d'une matrice. Comment concevoir un algorithme pour trouver une partition optimale qui minimise $ somme (m [1 ... x_1,1 ... x_1]) + somme (m [x_1 ... x_2, x_1 ... x_2]) + ... + somme (m [x_k ... n, x_k ... n]) $

Pour visualiser, découvrez une partition qui minimise la somme de tous les éléments ombragés du tableau ci-dessous

Answer 1

Tout d'abord, nous notons que avec $ \ mathcal {o} (n ^ 2) $ précomptes, où nous stockons les «SUMS PREFIX», nous pouvons trouver le < un href="https://www.geeksforgeeks.org/submatrix-sum-queries/" rel="nOfollow noreferrer"> somme de tous les éléments d'un sous-programme carré donné dans $ \ mathcal {o} (1) $ temps.

Maintenant, laissez $ dp [i] $ soit la réponse optimale, si la matrice d'entrée n'avait que la première $ I $ lignes et première $ i $ colonnes. La réponse finale que nous recherchons est $ dp [n] $ .

Le cas de base serait $ dp [0]= 0 $ .

Pour calculer $ dp [i] $ , nous iTerons sur tout $ j $ telle que < SPAN CLASS="MATH-CONTAINER"> 1 $ \ LE J \ LEQ I $ , et nous considérons le dernier intervalle de la partition d'être $ [j, i] $ . Pour une $ J $ , la somme minimale serait $ DP [J-1] + somme (m [j \ ldots i] [j \ ldots i]) $ . Donc cela conduit à l'équation

$$ dp [i]=min_ {1 \ Leq j \ leq i} (DP [J-1] + somme (m [j \ ldots i] [J \ ldots i])) $$

donc, $ dp [i] $ peut être calculé dans $ \ mathcal {o} (n) $ < / span> temps, et tout le problème prend $ \ mathcal {o} (n ^ 2) $ temps et espace.