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?
Finding dynamic programming algorithm
dynamic programming;space complexity
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.  