Can the unbounded knapsack problem be described as a matrix exponentiation?

Question

It seems that the general approach to a dynamic programming problem is to formulate a recurrence relation and then either implement a top down recursive solution or a bottom up iterative solution.

But if there's a recurrence relation I think that means we could potentially represent the problem as a state vector and a matrix updates the state through a multiplication. This approach can be used to generate the Fibonacci sequence for example.

Can this linear algebra approach be applied generally to any dynamic programming problem such as the unbounded knapsack problem?

Answer 1

For the Fibonacci sequence, the recurrence relation is linear. That's why it can be represented as a matrix representation, i.e., using linear algebra. If the recurrence relation isn't linear, you can't do something like that.

So, no, you can't always do that.