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!

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


Your Answer

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

Browse other questions tagged or ask your own question.