A Graphical Introduction to Dynamic Programming

Coin Change

https://avikdas.com/2019/04/15/a-graphical-introduction-to-dynamic-programming.html

Two ways to solve this ($d$ is the set of denominations, $t$ is the target, and $i$ is the last index in $d$ [assuming sorted ascending]):

$f(d,t) = \min{\begin{cases}f(t - d_0)+1\f(t - d_1)+1\…\f(t - d_n)+1\end{cases}}$

$f(i,t) = \min{\begin{cases}f(i, t - d_i) + 1\f(i - 1, t)\end{cases}}$

The first method recursively diminishes the target value until it gets to zero. Each choice is “what denomination do we use at this step?”.

The second recursively diminishes the set of denominations that we’re still picking from. Each choice is “do I still use this (largest) denomination, or do I discard it and only use smaller denominations from here on out?”

I don’t think you can memoize the first because $f(d, t)$ can become more optimal as you explore more of the search space, but $f(i, t)$ doesn’t change (at least can’t get smaller because we’re going from the largest denomination down to the smallest) once calculated.