# Improving Skill in Solving Dynamic Programming Q

Do you think it is possible to get better, inherently, in solving dynamic programming problems, or at best we can do is just recognizing patterns (since it is completely a matter of innate talent to get creative in solving problems we have never seen before)?

Any suggestion to improve this skill? Thanks!

Does a chess player just memorize patterns? Thatâ€™s part of it, but theyâ€™re also developing the ability to see ideas and processes and consequences and develop intuition.

With dynamic programming, yes, learning certain patterns and how to apply this is definitely part of it. But youâ€™re also training parts of your brain to think that way.

I used to teach guitar. My favorite was teaching jazz guitar and improvisation. The great jazz trumpeter Clark Terry once said: imitate, assimilate, innovate. I think the same thing applies. Students would learn and practice licks, transcribe solos, etc. Gradually they learn to think like the masters and it just becomes part of their thought process.

1 Like

Of course you can improve. However, itâ€™s best to approach from first principles rather than trying to memorize a set of patterns that â€ślookâ€ť like dynamic programming. That is, you need to really understand whatâ€™s going on and how the technique works. That will make it much easier to apply to problems youâ€™ve never seen before.

So firstly, dynamic programming is an optimization technique â€“ hence â€śprogramming.â€ť You can essentially forget the â€śdynamicâ€ť part. That was included to set the technique apart from linear programming (the dominant technique at the time) and to bamboozle the DoD. But hereâ€™s the key point: if youâ€™re problem isnâ€™t an optimization problem or canâ€™t be converted into one, dynamic programming is the wrong technique.

Secondly, dynamic programming assumes a certain problem structure. In particular, the problem can be decomposed into subproblems that have the same structure (so recursion, effectively) and the optimal solution of the problem is composed of optimal solutions to the subproblems. This recursive structure is built into the Bellman equations used to solve dynamic programming problems. Classic examples include shortest-path routing and 0-1 knapsack problems.

Thirdly, thereâ€™s a bit of an art to defining the cost function, state variables, and so on such that the problem fits the mold of dynamic programming. You can practice this. And this is really the hard part. If you botch the modeling, the math wonâ€™t work out. Get the modeling right, and the math is algorithmic â€“ mechanical.

Youâ€™ll note I havenâ€™t yet mentioned things like memoization or tableauxâ€™s. Thatâ€™s because they donâ€™t really have anything to do with dynamic programming per se. Those are simply techniques we use to implement dynamic programming on a computer. Fundamentally, the technique is mathematical in nature.

Bottom line, there are two things to do to improve:

1. Really learn whatâ€™s going on under the hood
2. Practice modeling

Most undergraduate CS courses spend a lecture or two on dynamic programming. Contrast that with the ops research community where there are entire graduate courses. Itâ€™s a deep subject. Hope this helps.

jrm

1 Like

Thanks. I forgot that we learn the forms to master the formless. Thanks!

Thanks. One of my biggest problem is visualizing what is and should happen, the stack, and so on. They are already difficult on small test cases, and it gets irritating when my model works on small test case, but does not work on bigger bigger test cases, where I have to run numerous cycles until the problem started to be seen. Well, I guess in this case the only cure is just grit, time and patience then. Thanks!

Like anything else, practice makes better. If you need to, start with small, easy problems and spend some time there.

2 Likes

Hey, to get better at Dynamic Programming or any DSA topic for that matter, there should be consistency in problem-solving.
Be a part of some coding community, where you can actively ask doubts whenever you are stuck or need help with an approach.

I have yet to practice what I just preached:P

But on a serious note:
Find resources online where theyâ€™ve mentioned previous interview questions like this: https://www.interviewbit.com/courses/programming/dynamic-programming/#dynamic-programming-interview-questions
or check out video tutorials for understanding concepts, my personal fav youtube: https://www.youtube.com/watch?v=BCO8JKA2_N8

but then it takes a lot of effort and time to master any concept.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.