3
$\begingroup$

I got a matrix of integers of size $3\times n$. Of each one of the three rows, for each column I got to choose one number, with the restriction that, for each $i$, the numbers chosen in the $i$th and $(i+1)$st rows cannot come from the same column.

The problem asks to make an algorithm such that the summation of all the numbers I've chosen is the minimum possible, has time complexity $O(n)$ and space complexity of $O(1)$.

I know how to do this with dynamic programming, in a more classical way: I calculate the sub-problems, store the results in a matrix of size $3\times n$ until the matrix is complete, then the result is the minimum value of the last row.

The problem is that will have space complexity of size $O(n)$, what I'm not seeing?

$\endgroup$
2
  • 4
    $\begingroup$ Perhaps I misunderstand. For each column you choose one of the three numbers so the total is minimal? Just choose the smallest in each column seems to be the solution. Unless you have other constraints? $\endgroup$
    – Hendrik Jan
    May 16, 2014 at 23:23
  • $\begingroup$ Yes, silly me. The constrain is that you can't choose two consecutive numbers of the same row. For example, I can't choose from col $1$ the first row, and from col 2, the first row again. $\endgroup$
    – FranckN
    May 17, 2014 at 9:28

1 Answer 1

Reset to default
4
$\begingroup$

Run along the columns of the matrix keeping three numbers. For each row determine the minimum score assuming the last number chosen came from that row.

$\endgroup$

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.