0
$\begingroup$

I know there alot of questions on Dynamic Programming and I feel I have a handle on the theory, use the answers from sub problems to answer the current problem, without the redundancy of recursion. My confusion comes from implementation. Here is a specific question. Every question I look at builds its grid differently, for example, 0,1 knapsack you go back down the row and up one. For coin changing its just back down the row. For Fibonacci and stair steps its the sum of the last two. If I am tasked with a Dynamic Programming problem is there any kind of base approach I can take to building out my grid?

$\endgroup$
1
1
$\begingroup$

One easy way to do dynamic programming is memoization -- just do the regular recursion, but store any results computed and reuse them if the same (sub)problem shows up. Recursion is at the very hearth of dynamic programming, what is usually programmed is a careful unrolling of the recursion.

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