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.
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:
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
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.
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.