1
$\begingroup$

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!

Improve this question
$\endgroup$
4
  • 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

0

Reset to default

Your Answer

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