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

Question

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

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.