Problem

  • Given a set of infinite coins
  • Find the minimum number of coins to making change for a specific amount of money, without considering the order of the coins

Example

  • Input: given a set of infinite coins {2, 3, 1}. Find the minimum number of coins of making change for 3
  • Expected output: 1
  • Explanation: there're 3 ways to making change for 3: {3}, {1, 1, 1}, {1, 2}, minimum is {3}

Approach

  • To making change for a value i, need to use coins with value less than or equal to i

  • For each coin in the set c[j], calculate the minimum number of coins to making change m[i] = Math.min(m[i], m[i - c[j]]) + 1 with c[j] <= i <= target, m[0] = 0 is base case, m[target] is the final result

Implementation


Complexity

  • Time complexity: O(nm) with n is the change target, m is the number of coins
  • Space complexity: O(n) with n is the change target

References