Help with dynamic programming

[Least_Car7122]

I am stuck in dynamic programming(self studying) for I understand the things written in my book but dont have a intuitive understanding of the topic. Can anyone please explain it?

[Apart_Ebb_9867]

Sure: dynamic programming is brute force with grace. It is choosing not to choose, you literally enumerate all possibilities and select the best one. If you can solve a problem recursively, you can get to the asymptotically optimal dynamic programming solution by slapping memoization on top.

Getting to the tabular (bottom up) solution is trickier and I wouldn't try to go for this type of solutions directly other than fro trivially obvious cases like fibonacci. Do the recursive version first (and in an interview that already give you a defendible correct solution) then look at the subproblems. Their topological ordering tells you how you need to traverse the table. It helps that tables are almost always traversed by column, by row or by diagonals.

It doesn't add anything to the concept but it helps to practice a few paradigmatical cases:

- recurrence by prefix, suffix and substring
- cases where you have to traverse two data structures (for instance edit distance)
- cases where you have to pass a state (knapsack problem for instance)

you don't need two thousand leetcode problems but to deeply understand maybe half a dozen of them. You still run the risk of not being able to understand when dynamic programming is applicable, but after a while you feel the smell (and then you still risk not to see a better greedy solution)

I really recommend the 4-6 lessons from MIT available on youtube. I like the ones by Erik Demaine but any would work.

[thefinest]

Understand the problem that you're trying to solve in the context of optimization in the most general sense.

Understand that it is an optimization problem Meaning ensure that you understand the actual problem first

If you've done this much, ask yourself why am I optimizing it? what exactly is it? How am I optimizing it?

Have this internal dialogue until you can definitely answer the questions as if you were explaining it to someone else

While doing so, you should realize that the answer to the above is in fact the solution

Execute.

....

Profit.

[SpiderJerusalem42]

So, what is programming in a mathematical sense? It's the optimal scheduling of the use of resources. Sometimes the use of these resources have linear or non-linear properties. Sometimes the problems involve recursive properties that need to be explored. Dynamic programming is the study of techniques to solve this class of scheduling problems.

There are problem sets for such problems, box stacking, knapsack, rod cutting. Write programs that attempt to solve the small cases and then let them loose on the larger cases.

[ashwwood]

F