It's an O(n) algorithm - although there is an inner loop - since the number of coin values is fixed it's still a linear algorithm

So it's a very fast algorithm.

The basic approach with dynamic programming is:

Start from the bottom and save the base case results.

Go to the "nest level" and calculate those results based on the previously stored results.

Keep going until you get your answer.

The i - loop represents the amount of change to be given

The j - loop represents how many distinct coin values there are. Note that isn't the number of coins in change given its how many coin values you have.

The insight is that to calculate how many ways to give change for a given amount using coins of specific values:

a) Use 1 of your coins and deduct that from the amount.

Result for a) is 1 + ways to count (amount - coin used). e.g. for 57¢ - you can use 1¢ and calculate 56¢.

Those results are stored in the results[i] - since python doesn't have native arrays result is a list of lists

b) Result for b) is how many ways can you give change by ignoring all coins of one specific value.

e.g. for 57¢ - how many ways can you give change when you NEVER use any 1¢ coins?

Those results are stored in the result[amount] list indexed by how many coin values are used

For a given amount and given number of coin values total = a) + b)

To find how many ways to count 10¢ using 1¢, 5¢, 10¢, 25¢, 50¢

Build up the result 'array' like this

How many ways to give 0¢ change

result[0] = [1, 1, 1, 1, 1, 1] -

there is 1 way of giving 0¢ change with a 0¢ coin

there is 1 way of giving 0¢ change with 0¢ and 1¢ coins.

there is 1 way of giving 0¢ change with 0¢, 1¢, 5¢ coins...

How many ways to give 1¢ change

result[1] = [0, 1, 1, 1, 1, 1] -

there is no way of giving 1¢ change with a 0¢ coin

there is 1 way of giving 1¢ change with with 0¢ and 1¢ coins

there is 1 way of giving 1¢ change with with 0¢, 1¢, 5¢ coins...

these don't change until we hit 5¢

result[5] = [0, 1, 2, 2, 2, 2] -

there is no way of giving 5¢ change with a 0¢ coin

there is 1 way of giving 5¢ change with with 0¢ and 1¢ coins

there are 2 ways of giving 5¢ change with with 0¢, 1¢, 5¢ coins...

these don't change until we get to 10¢

result[10] = [0, 1, 3, 4, 4, 4] -

there is no way of giving 10¢ change with a 0¢ coin

there is 1 way of giving 10¢ change with with 0¢ and 1¢ coins result

there are 3 ways of giving 10¢ change with with 0¢, 1¢, 5¢ coins

there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢ coins

there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢, 25¢ coins

there are 4 ways of giving 10¢ change with with 0¢, 1¢, 5¢, 10¢, 25¢, 50¢ coins.

Since we want to know how many ways using all coins - the answer is at the last value in the last row which is 4.