Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Minimum Coin Change

Introduction

Given an infinite supply of ‘n’ coin denominations and a total money amount, we are asked to find the minimum number of coins needed to make up that amount.

Example 1:

Denominations: {1,2,3}
Total amount: 5
Output: 2
Explanation: We need a minimum of two coins {2,3} to make a total of '5'

Example 2:

Denominations: {1,2,3}
Total amount: 11
Output: 4
Explanation: We need a minimum of four coins {2,3,3,3} to make a total of '11'

.....

.....

.....

Like the course? Get enrolled and start learning!
L

Lucifer

· 4 years ago

Any idea why '+1' is added to count1 i.e. while including the coin at the current index?

Show 4 replies
A

Avinash Agarwal

· 4 years ago

class Solution { public int coinChange(int[] coins, int amount) { if(amount == 0) return 0; if(coins.length == 0 && amount > 0) return -1;

int[] dp = new int[amount+1];

Arrays.fill(dp, amount+1); dp[0] = 0;

for(int i=1; i

Online Courses

Online Courses

· 4 months ago

My solution from brute force to 1D tabular DP.

Time = O(N.T), where N is the number of denominations and T is the total

Space = 0(T) – for the final solution.

import math

class Solution:
  def countChange_bruteforce(self, denominations, total):
    n = len(denominations)

    def minCoins(idx, current_sum):
      if current_sum == total:
        return 0

      if idx >= n:
        return float('inf')
      
      skip_count = minCoins(idx + 1, current_sum)
      
      current_sum += denominations[idx]
      take_count = float('inf')
      if current_sum <= total:
        take_count = 1 + minCoins(idx, current_sum)
      
      count = min(skip_count, take_count)

      return count
    
    result = minCoins(0, 0)
    return result if result != float('inf') else -1