Comment by zzzeek

It's usually covered in a first or second year algorithms course. It's a recursive problem definition paired with tabling to eliminate redundant work. Critically, the recursive subproblems have to be overlapping (they'll do some of the same work as the other recursive steps) to see any benefit. You can implement it top-down and add a cache (memoization) or you can implement it bottom-up and fill out the table iteratively rather than through recursion.

If you just implement it recursively without tabling then you end up re-doing work and it's often an exponential runtime instead of polynomial.

To clarify on overlapping, consider Fibonacci:

  F(n) = F(n-1) + F(n-2) # and the base cases

F(n-1) includes F(n-2) in its definition, and both F(n-2) and F(n-1) include F(n-3). If you implement this naively it produces an exponential runtime. Once you add the table, the single initial recursive call to F(n-1) will end up, through its chain of calls, storing the result of F(n-2) and now the implementation is linear instead of exponential.

> Read wikipedia and it seems to mean....use a recursive function?

Yes, that's one (common) approach to dynamic programming. The recursive function call are memoized so that previous calculations are remembered for future function calls. Overlapping subproblems become trivial if you can reuse previously computed values. The recursion with memoization is top-down dynamic programming.

The coin problem is like the intro to it. Try some of the codeforces one :skull: