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 at 13:34
  • $\begingroup$ @CodeChef the $k$ is not fixed, which can be one between $1$ and $n$ $\endgroup$ – Haohan Yang Apr 12 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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