Dynamic Programming is not black magic

https://qsantos.fr/2024/01/04/dynamic-programming-is-not-black-magic/ It’s good that the article points out that DP algorithms are “just” clever ways to cache a recursion. Looking for a recursive solution is certainly the best way to start out looking for a DP solution,

in my experience - if you can find one, memoising it is trivial and may give a big speedup (and may even be faster than a “bottom-up” DP, since it only ever computes solutions that we definitely need). With enough practice, it’s usually possible to come up with a (correct but slow) recursive solution.

When turning this into a DP, it doesn’t matter if there are large numbers of subproblems in the call tree – what’s important is that there are a relatively small number of distinct subproblems. (Since there’s no point caching a result that’s only ever needed one time.) And that’s where the difficulty tends to lie: Figuring out how to partition the original problem into few enough distinct subproblems.