Problem statement

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.
Link to problem

Example 1

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2

Input: coins = [2], amount = 3
Output: -1

Solutions

Approach 1: Dynamic Programming

This was a tough one, there’s two approaches in DP, bottom-up and top-down.
I wasted too much time on one approach because even though the concept itself is pretty easy, coding that proved quite challenging and I resorted to a simple implementation. I couldn’t wrap my head around using DFS because even though it was the simplest approach, I failed to implement it. Perhaps I’ll give it a shot on Sunday.

Anyway, the heart of the problem is knowing how to add up to the amount given, while starting at 0.
You essentially add one coin whenever you pick a coin and check if that particular coin that you picked had any previous.. results. Perhaps a pseudocode or an example might be helpful.

Example:
coins = [1, 3, 4, 5]
amount = 7

Start with an array that has same amount of entries as amount + 1, with the values amount + 1
In this case, consider dp = [8, 8,...8]

Start at the bottom, so dp[0] = 0
Now start looking at your coins and see what you can cook with them
dp[1] = you pick a coin that does not exceed 1, that's 1 coin
dp[1] = 1 

dp[2] = there's no 2 coin so you pick the 1 coin and another 1 coin
dp[2] = 2

dp[3] = there is a threes coin so you pick that one up
dp[3] = 1

dp[4] = there is a fours coin so you pick that one up
dp[4] = 1

Now that our target is 7
we need to find out what dp[7] is, and for that we need to compare all the coins
and check what we found above
Following are some of the outcomes including optimal one:

dp[7] = 1 + dp[7-1] - the 1 denotes value one, so a coin with value one, and now we are left with 6
    dp[6] = 2
dp[7] = 3
Is that an optimal one? Perhaps, but lets keep going.

dp[7] = 1 + dp[7-3]
    do[4] = 1
dp[7] = 2
Oh neat, we found something better, is there a better one?

dp[7] = 1 + dp[7-4]
    dp[3] = 1
dp[7] = 2
Same as above, essentially the same combination 

dp[7] = 1 + dp[7-5]
    dp[2] = 2
dp[7] = 3
Back to three, so not optimal

And we found our minimum combo, which is (3, 4).

Implementation in Rust

fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let mut dp = vec![amount + 1; amount as usize + 1];
    dp[0] = 0;
    
    for i in 1..(amount + 1) {
        for coin in &coins {
            if (i - coin) >= 0 {
                dp[i as usize] = std::cmp::min(dp[i as usize], dp[(i - coin) as usize] + 1);
            }
        }
    }

    if dp[amount as usize] != amount + 1 {
        dp[amount as usize]
    } else {
        -1
    }
}

Time Complexity: $O(n\times{m})$
$n = amount$
$m = coins$
Space Complexity: $O(n)$
Runtime on LeetCode: $12$ms