Day 1 : 322. Coin Change

Given an array of coins representing different denominations, and a target amount of money, return the minimum number of coins needed to reach that amount. 

If it’s not possible to make up the amount, return -1.

Before we dive in,

Breathe

Just know it took me a full day to understand this problem, so if I don’t explain it correctly, it’s on me. Not on you.

Now, let’s think about the problem before diving into it.

We are asked to find the minimum number of coins when summed it equals the amount.

Let’s think about the problem together before we jump into coding. We’re asked to find the minimum number of coins that sum up to a specific amount.

Given this example:

coins = [1, 2, 5]
amount = 11

We could try using 11 coins of 1 (like 1 + 1 + 1 + ...) or maybe 1 + 5 + 2 + 1 + 1 + 1. Both add up to 11, but we want to find the solution that uses the fewest coins.

A brute-force approach would involve finding all possible combinations and then identifying the one with the least coins. However, this would take a massive amount of time.

Instead, let’s use a dynamic programming (DP) approach to solve this by breaking the problem into smaller subproblems.

Here’s the plan:

1. Define an array dp where dp[i] represents the minimum number of coins needed to reach the amount i.

2. Set dp[0] = 0 because no coins are needed to make an amount of 0.

3. Initialize all other entries in dp to a large number, like 100005, to signify that we haven’t yet found a way to reach those amounts.

For each coin value, we’ll update our dp array, keeping track of the minimum coins needed to reach each amount.

For example, with coin = 1:

• dp[0] = 0 (no coins needed for 0)

• dp[1] = 1 (we need 1 coin of 1 to make an amount of 1)

• dp[2] = 2 (we need 2 coins of 1 to make an amount of 2)

• … and so on until we reach dp[11] = 11.

dp = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Now let’s introduce a second coin, coin = 2, which gives us more efficient ways to reach certain amounts. For example:

• dp[2] could now use 1 coin of 2 instead of 2 coins of 1.

• dp[3] could use 1 coin of 2 and 1 coin of 1, making it more efficient.

The general update rule for any position i in dp is:

dp[i] = min(dp[i], dp[i-coin] + 1)
        ↑         ↑         ↑
    Current     Previous    New coin
    Best        Best       we're adding

This rule allows us to find the optimal number of coins needed to reach each amount by checking if adding a coin of a certain denomination gives a better solution.

Now, where would our answer be?

Remember dp[i] ……

Complete Solution :

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int>dp (amount+1, 100005);
        dp[0] =0; 
        for(auto coin: coins){
            for(int x=coin; x<=amount; x++){
                if(!(dp[x-coin]==100005)){
                    dp[x] = min(dp[x], dp[x-coin]+1);
                }
            }
        }
        if(dp[amount]==100005){
            return -1;
        }
        return dp[amount];
       
    }
};

Self-gaslight of the week

I truly believe you can gaslight yourself to success.

1. Make space for the emotions you crave

2. USE QWOTED to find questions you can answer to become a thought leader

Jobs and Scholarships

1. New scholarships of this week!

2. Entry level jobs!!