2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\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.