Coin Change problem, From LeetCode 518

Source of the question: https://leetcode.com/problems/coin-change-2/

There have been plenty of docs online to discuss about this problem. Of course, the correct solution is to use DP, which is both time / memory efficient:

class Solution {
   public int change(int amount, int[] coins) {
      int[] dp = new int[amount + 1];
      dp[0] = 1;
      for (int coin : coins)
         for (int i = 0; i <= amount - coin; ++i)
            dp[i + coin] += dp[i];
      return dp[amount];
    }
}

To get more, I would like to analyze this problem in a more theorical / mathematical way.

First let’s solve the specific question : Coins are given (For example, coins=[1, 2, 5]).

There is a theorem that to get the ways of combination, we can get it by the coefficient of the polynomial. For the above question, to change to 1 cent, it can be represented as

(x⁰ + x¹ + x² + ….. )

Similar, to change with 2 cent, can be represented as (x⁰ + x² + x⁴ + ….)

And to change with 5 cents, can be represented as (x⁰ + x⁵ + …)

To get the change of n cents with [1, 2, 5] cent, is to get coefficent of x^n the product of

(x⁰ + x¹ + x² + ….. )(x⁰ + x² + x⁴ + ….)(x⁰ + x⁵ + …)

Then we can write the first program.

Run the problem. Same result of the 2 methods (change_dp and change_1).

But we can improve change_1. We can use mathematical knowkedge to operation the expression above, as:

And A(x) = 1+x+2x²+2x³+3x⁴+4x⁵+5x⁶+6x⁷+7x⁸+8x⁹+7x¹⁰+8x¹¹+7x¹²+8x¹³+7x¹⁴+6x¹⁵+5x¹⁶+4x¹⁷+3x¹⁸+2x¹⁹+2x²⁰+x²¹+x²²

The SUM part, can provide x⁰, x¹⁰, x²⁰, … etc. The A(x) part, provides the reminder part.

For example, for the above expression, if we want to calculate x²⁰.

It can be x⁰ * x²⁰ , or x¹⁰ * x¹⁰, or x²⁰ * x⁰.

The coefficient of A(x) for x¹⁰ and x¹⁰ and x²⁰ = [1, 7, 2].

And for the sum part, x²⁰ and x¹⁰ and x⁰, k=[2, 1, 0].

So the coefficient of x²⁰ of the whole expression, is

1 * (2 + 2, 2) + 7 * (2 + 1, 2) + 2 * (2, 2) = 1 * 6 + 7 * 3 + 2 = 29.

which means, to change 20 cents with [1, 2, 5] cents, it can be 29 combination.

with this alogrism, we can write a new function :

Now lets analysis the performance for the 3 ways.

for the DP solution, its O(amount * coin_count);

for the change_1, it is O( (amount / coin[1])*(amount / coin[2])* (amount / coin[3])*…*(amount / coin[n])).

for the change_2, it is O(1). Because no matter how big amount is, it uses same time.

Add some code to get the execution time.

And the time (nano-second) is :

500040001,500040001,500040001
dp: 2592200
change_1: 16576463200
change_2: 21300

Of course, change_2 is the best. Far more faster than dp / change_1.

Then lets go to the generic question : If the coins is not fixed, but changable.

Assume that we need to change amount cents to n coins : {c(0), c(1), c(2)…. c(n-1)}. How to solve ?

Then the above expression is equal to