C++: Coin Change

Thought Process

The problem requires finding the minimum number of coins needed to make up a given amount. We use a dynamic programming to solve this. Create a 2D array 't' where t[i][j] represents the minimum number of coins required to make amount 'j' using the first 'i' coins. We initialize the array such that if no coins are available, the required number of coins is infinite. If the amount is zero, no coins are needed. We then fill the table by considering whether to include or exclude each coin, ensuring we always choose the minimum number of coins. 

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
    
        int noOfCoins = coins.size();
        int t[noOfCoins+1][amount+1];
        int infinite = 1e9;

        // If number of coins is zero then theoretically, no. of coins 
        // required to make the amount = infinite
        for(int i=0;i<=amount;i++)
            t[0][i] = infinite;

        // If Amount is zero then number Of coins required to make the amount = 0
        for(int i=0;i<=noOfCoins;i++)
            t[i][0] = 0;

        for(int i=1;i<=noOfCoins;i++){
            for(int j=1;j<=amount;j++){

                if(coins[i-1]>j)
                    t[i][j] = t[i-1][j];
                else
                    t[i][j] = min(t[i-1][j],1 + t[i][j-coins[i-1]]);
            }
        }
        if(t[noOfCoins][amount] != infinite)
            return t[noOfCoins][amount];
        else
            return -1;
    }
};

Code Complexity

Time Complexity: O(n * amount)

The algorithm iterates through each coin and each possible amount, resulting in a time complexity of O(n * amount).

Space Complexity: O(n * amount)

The algorithm uses a 2D array of size (n+1) x (amount+1) to store intermediate results.

Code copied!