# Partition the indices of 2d array to minimize sum of sub-matrices

Given an $$n\times n$$ Matrix $$M$$, and the indices $$[{1,2,3,4,...,n}]$$ are divided into several intervals : $$[1,x_1],[x_1,x_2],...[x_k,n]$$, which further extract several squared sub-matrices along the $$M$$'s diagonal - $$M[1...x_1,1...x_1],M[x_1...x_2,x_1...x_2],...M[x_k...n,x_k...n]$$.

Suppose $$Sum(Matrix)$$ is the sum of all elements in a matrix. How to design an algorithm to find out an optimal partition that minimizes $$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])$$

To visualize , find out a partition that minimizes the sum of all shaded elements in the table below

• Does the partition have to have exactly $k$ intervals, or is that not fixed? Apr 12 '20 at 13:34
• @CodeChef the $k$ is not fixed, which can be one between $1$ and $n$ Apr 12 '20 at 14:27

First we note that with $$\mathcal{O}(n^2)$$ precomputation, where we store the 'prefix sums', we can find the sum of all the elements in a given square subgrid in $$\mathcal{O}(1)$$ time.
Now, let $$DP[i]$$ be the optimal answer, if the input matrix had only the first $$i$$ rows and first $$i$$ columns. The final answer that we are looking for is $$DP[n]$$.
The base case would be $$DP[0] = 0$$.
To compute $$DP[i]$$, we iterate over all $$j$$ such that $$1 \le j \leq i$$, and we consider the last interval in the partition to be $$[j, i]$$. For a fixed $$j$$, the minimum sum would be $$DP[j-1] + Sum(M[j \ldots i][j \ldots i])$$. So that leads to the equation
$$DP[i] = \min_{1\leq j \leq i} (DP[j-1] + Sum(M[j \ldots i][j \ldots i]))$$
So, $$DP[i]$$ can be computed in $$\mathcal{O}(n)$$ time, and the whole problem takes $$\mathcal{O}(n^2)$$ time and space.