A wise man once said:

Locally optimal choices don't guarantee globally optimal solutions

If you have denominations of 10, 30 and 40 and wanna have 60 with least number of coins, and you have eyes, you know it's two 30s.

But a computer needs to go by certain rules, it can't eyeball (well, AI... let's not go there today). And once you have set the rule, it will give the correct answer when there are thousands of denominations and a huge number to add up to, which you won't be able to unless you're one of those possessed Abacus kids in those counting competitions.

So let's see what that computer logic is. If you ask your computer to be greedy and go by the largest denomination first, it will choose 40, have 20 left and will be forced to choose two 10s, totalling 3 coins and thus not giving the optimal solution. And now re-read that wise man's quote.

Anyway, we gotta be smarter than that. Now you know what sub-topic is question is under, but we really need to justify why we should be using Dynamic Programming here. It is easy to memorise and move on, but is that true learning?

So, let's look at it. To make amount n with minimum coins, we need to first try using each available coin denomination. Then for each coin we use, we need the minimum coins for the remaining amount and we pick the option that gives us the overall minimum.

Of course since brute forcing this gives a stupid O(coins ^ amount) time complexty, we can, most of the time, substitute such an approach with such conditions with a recursive relationship:

minCoins(amount) = 1 + min(minCoins(amount - coin)) for all coins ≤ amount

Makes sense? Let's go through a dry run: let's say we have denominations [1, 3] and we want 4.

Step 1: minCoins(4). We need to try each coin ≤ 4:

Use coin 1: 1 + minCoins(4-1) = 1 + minCoins(3)
Use coin 3: 1 + minCoins(4-3) = 1 + minCoins(1)
So: minCoins(4) = 1 + min(minCoins(3), minCoins(1))

Step 2: Need minCoins(3). Try each coin ≤ 3:

Use coin 1: 1 + minCoins(3-1) = 1 + minCoins(2)
Use coin 3: 1 + minCoins(3-3) = 1 + minCoins(0)
So: minCoins(3) = 1 + min(minCoins(2), minCoins(0))

Step 3: Need minCoins(2). Try each coin ≤ 2:

Use coin 1: 1 + minCoins(2-1) = 1 + minCoins(1)
Coin 3 > 2, so skip
So: minCoins(2) = 1 + minCoins(1)

Step 4: Need minCoins(1)

Try each coin ≤ 1:
Use coin 1: 1 + minCoins(1-1) = 1 + minCoins(0)
Coin 3 > 1, so skip
So: minCoins(1) = 1 + minCoins(0)

Step 5: Base case minCoins(0)

minCoins(0) = 0 (need 0 coins to make amount 0)

Now let's trace back up:

minCoins(1):

minCoins(1) = 1 + minCoins(0) = 1 + 0 = 1

minCoins(2):

minCoins(2) = 1 + minCoins(1) = 1 + 1 = 2

minCoins(3):

minCoins(3) = 1 + min(minCoins(2), minCoins(0))
            = 1 + min(2, 0)
            = 1 + 0 = 1

minCoins(4):

minCoins(4) = 1 + min(minCoins(3), minCoins(1))
            = 1 + min(1, 1)
            = 1 + 1 = 2

Final Answer

minCoins(4) = 2

Did you spot the inefficiency here?? We are solving the same sub-problems over and over again!!

minCoins(4)
├── minCoins(3)
│   ├── minCoins(2)
│   │   └── minCoins(1)  ← computed here
│   └── minCoins(0)
└── minCoins(1)  ← computed again here!

This is exactly what we needs must fix! Matter of fact, recursive relationship here will still take O(coin ^ amount) time complexity. In the Longest Common Subsequence problem, recursion did make things slightly better, but here not even that!

And as a general rule of thumb, if we are solving the same sub-problems over and over again, dynamic programming is always a possibility for a solution.

And I get it. You can't come up with a DP solution organically. It's a high IQ game out here. You either crack a puzzle with some weird brain magic or you just give up. Yes, if you consider Recursion + Memoisation to be DP, please, stop it. It is a solution, of course optimal, but it ain't DP sorry, it's called a coping mechanism.

Let's explore memoisation optimisation anyway.

unordered_map<int, int> memo;
int solve(int amount) {
    if (amount == 0) return 0;
    if (memo.count(amount)) return memo[amount];
    
    int result = INT_MAX;
    for (int coin : coins) {
        if (coin <= amount) {
            result = min(result, 1 + solve(amount - coin));
        }
    }
    return memo[amount] = result;
}

Without memoisation:

solve(6)
├── solve(5)
│   ├── solve(4)
│   │   ├── solve(3) ← computed
│   │   ├── solve(1) ← computed  
│   │   └── solve(0)
│   ├── solve(2)
│   │   └── solve(1) ← computed AGAIN
│   └── solve(1) ← computed AGAIN
├── solve(3) ← computed AGAIN
└── solve(2)
    └── solve(1) ← computed AGAIN

With memoisation:

solve(6)
├── solve(5) ← computed once, stored
├── solve(3) ← computed once, stored  
└── solve(2) ← computed once, stored
    └── solve(1) ← computed once, stored
        └── solve(0) ← base case

All future calls to solve(5), solve(3), solve(2), solve(1) = O(1) lookup!

Turns out it is a glorified term for storing these re-usable solutions in a hashmap. I used to think it was some incredible concept, some universal pattern to solve any DP problem, but it is the most disgusting escapist way to ruin elegance once I learnt what it actually is.

So, finally, here's the real beauty:

for (int i = 1; i <= amount; i++) {
    for (int coin : coins) {  // Try each coin
        if (coin <= i && dp[i - coin] != INT_MAX) // Can we use this coin?
            dp[i] = min(dp[i], dp[i - coin] + 1);
    }
}

Yes, it is 100% true that DP has no tried and tested real formula to find a truly bottom up solution. These are things made for mathematical purists and puzzle enthusiasts but sadly commoditised by the Software Dev interview industry to see how many of these solutions can be memorised by gulpers for an added level of complexity to filter out more people who are actually interested in truly contributing something to the world, and instead hire rote learners.

In DP's defense, once someone solves enough problems, apparently it becomes a game of pattern recognition, some Aha moment which I'm yet to reach. Will update if I do I guess. So yea I'm ending my rant here with a dry run for this:

Initialization: dp = [0, ∞, ∞, ∞, ∞, ∞, ∞]

i = 1: Try coins [1, 3, 4]

coin = 1: dp[1] = min(∞, dp[0] + 1) = min(∞, 1) = 1
coin = 3: 3 > 1, skip
coin = 4: 4 > 1, skip

dp = [0, 1, ∞, ∞, ∞, ∞, ∞]

i = 2: Try coins [1, 3, 4]

coin = 1: dp[2] = min(∞, dp[1] + 1) = min(∞, 2) = 2
coin = 3: 3 > 2, skip
coin = 4: 4 > 2, skip

dp = [0, 1, 2, ∞, ∞, ∞, ∞]

i = 3: Try coins [1, 3, 4]

coin = 1: dp[3] = min(∞, dp[2] + 1) = min(∞, 3) = 3
coin = 3: dp[3] = min(3, dp[0] + 1) = min(3, 1) = 1
coin = 4: 4 > 3, skip

dp = [0, 1, 2, 1, ∞, ∞, ∞]

i = 4: Try coins [1, 3, 4]

coin = 1: dp[4] = min(∞, dp[3] + 1) = min(∞, 2) = 2
coin = 3: dp[4] = min(2, dp[1] + 1) = min(2, 2) = 2
coin = 4: dp[4] = min(2, dp[0] + 1) = min(2, 1) = 1

dp = [0, 1, 2, 1, 1, ∞, ∞]

i = 5: Try coins [1, 3, 4]

coin = 1: dp[5] = min(∞, dp[4] + 1) = min(∞, 2) = 2
coin = 3: dp[5] = min(2, dp[2] + 1) = min(2, 3) = 2
coin = 4: dp[5] = min(2, dp[1] + 1) = min(2, 2) = 2

dp = [0, 1, 2, 1, 1, 2, ∞]

i = 6: Try coins [1, 3, 4]

coin = 1: dp[6] = min(∞, dp[5] + 1) = min(∞, 3) = 3
coin = 3: dp[6] = min(3, dp[3] + 1) = min(3, 2) = 2
coin = 4: dp[6] = min(2, dp[2] + 1) = min(2, 3) = 2

Final result: dp[6] = 2

How surprising huh? That an obscure formula no one could ever come up by themselves yielded the correct result huh? Yea of course you understand how it works. How it basically recharges when it finds the next greater coin from the sheer beauty of the formula itself. Pretty cool ngl. Bye for now anyway.