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)?

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:

Really learn whatâ€™s going on under the hood

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.

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!