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

enter image description here

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

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.