# Sub-matrix with minimum size of $k$ and minimum sum

We have an $$n \times m$$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $$k$$ such that the sum of the entries in minimal. The answer to this problem is the sum of these entries.

My solution: Using dynamic programming, I have defined the sum of entries from the (0,0) entry to (i,j) as $$sum[i][j]$$. If the $$(i,j)$$ entry is $$entry[i][j]$$ then we have $$sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + entry[i][j]$$. Except, when either dimension of $$sum$$ is 0, the values are only the entries.

I do not know how to continue from here.

If you have a better idea for this problem, that would be appreciated too!

• What's the question? Apr 9, 2021 at 23:50
• How to find all the sub-matrices with at least k entriers.
– Pegi
Apr 9, 2021 at 23:51
• Can I use the "sum" array idea more efficiently?
– Pegi
Apr 9, 2021 at 23:58
• Please don't put your question or clarifications in the comments. Instead, edit the post to make it clear what your question is.
– D.W.
Apr 10, 2021 at 1:20