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?