Coin Change

Problem Statement: Coin Change

Coin Change Problem : You are given coins of different denominations, represented by an array - coins of size n. You are also given a value - target. 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.

Example: coins: [1,2,5], amount: 11

Output: Result: 3

Explanation: The Minimum coins needed are 5 + 5 + 1

Approach 1: Brute force

A trivial solution is to enumerate all subsets of coin frequencies that satisfy the constraints above, compute their sums and return the minimum among them.

To apply this idea, the algorithm uses backtracking technique to generate all combinations of coin. It makes a sum of the combinations and returns their minimum or −1 in case there is no acceptable combination.

The time complexity is exponential i.e. not the optimal one so we need to optimise it.

Approach 2: Dynamic programming

We note that this problem has an optimal substructure property, which is the key piece in solving any Dynamic Programming problems. In other words, the optimal solution can be constructed from optimal solutions of its subproblems.

For each value of amount from 1 to amount, we can choose any number of give coins of any type. We know that for 0 amount, min number of coins required = 0 ( dp[0] = 0 ). Then we calculate for the amount 1 by trying to take each coin and finally assigning the min coins amount to dp[1]. This process is repeated for all amounts till the given amount. Finally the required answer will be dp[amount] denoting minimum number of coins required to form the given amount.

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

class Solution(object):
    def coinChange(self, coins, amount):
        ways = [float('inf') for _ in range( amount + 1)]
        ways[0] = 0 # base case
        
        for coin in coins:
            for amt in range(1, amount + 1):
                if coin <= amt:
                    ways[amt] = min(ways[amt], 1 + ways[amt-coin])
        return ways[amount] if ways[amount] != float('inf') else -1
ob1 = Solution()
print(ob1.coinChange([5,2,4], 13))

Time Complexity: O(S∗n)where S is the amount, n is denomination count. In the worst case the recursive tree of the algorithm has height of S and the algorithm solves only S subproblems because it caches precalculated solutions in a table. Each subproblem is computed with n iterations, one by coin denomination. Therefore there is O(S∗n) time complexity.

Space Complexity: O(S), where S is the amount to change We use extra space for the memoization table.