4

Consider a below problem

Given an infinite number of nickels (5 cents) and pennies (1 cent). Write a code to calculate a number of ways of representing n cents.

My code

def coins(n):
    if (n < 0):
        return 0
    elif (n == 0):
        return 1
    else:
        if (cnt_lst[n-1] == 0):
            cnt_lst[n-1] = coins(n-1) + coins(n-5)
        return cnt_lst[n-1]

if __name__ == "__main__":
    cnt = int(input())
    cnt_lst = [0] * cnt #Memiozation
    ret = coins(cnt)
    print(ret)

Above approach counting repeated patterns more than one (obviously I'm not checking them explicitly).

[5,1,1,1,1,1] [1,5,1,1,1,1] [1,1,5,1,1,1], etc

Maintaining another list which holds the previously seen patterns will require a lot of memory as n grows. What another approach we can use to overcome this problem?

Improve this question
2
  • If n= total number of pennies, then n= (n/5) nickles +(n%5) cents. = for i= 0 to (n/5), n= (n/5-i) + ((n%5) + (5*i)), Can it be treated as (n/5)+1 ways of representing n cents with nickels and cents. (or) if n= k nickels and c cents, then n=k-(i) + c + 5*i, i varies from 0 to k.ie., k+1 ways of representing n cents. Does this look foolish? Commented Jun 23, 2016 at 6:45
  • Reducing memory further is not possible using this algorithm. However, there are other algorithms for this problem. Commented Jun 23, 2016 at 6:50

2 Answers 2

Reset to default
2

Instead of using a 1-dimensional list, you can use a 2-dimensional array where one dimension is the total, and the second dimension is the largest-value coin available.

Let's say C is your list of coin values in ascending order (in your example, C = [1, 5]). Then let A[i][j] be the number of ways to represent value i with coins 0 through j.

We know that for any j, A[0][j] = 1 because there is exactly one way to represent the value 0: no coins.

Now suppose we want to find A[8][1], the number of ways to represents 8 cents with pennies and nickels. Each representation will either use a nickel or it won't. If we don't use a nickel then we can only use pennies, so there are A[8][0] ways to do this. If we do use a nickel then we have 3 cents left so there are A[3][1] ways to do this.

To compute A[8][0] we only have one coin available so A[8][0] = A[7][0] = ... = A[0][0] = 1.

To compute A[3][1] we can't use a nickel since 3 < 5, so A[3][1] = A[3][0]. From there we have A[3][0] = A[2][0] = ... = 1 as above.

In general:

A[i][j] = A[i][j-1] if i < C[j]
          else A[i][j-1] + A[i-C[j]][j]

This algorithm works for any set of coin values.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

I get it what you are trying to say, But I think you meant C[j] > i. I tried implementing it with your approach here is my code paste.ofcode.org/AmkCtmpYHnK3kPNYLGp84n But I'm getting Stack Overflow error Error: RuntimeError: maximum recursion depth exceeded in comparison
@Atinesh No, C[j] < i is correct. If C[j] < i then we cannot use coin j so A[i][j] = A[i][j-1].
@Atinesh Your implementation is wrong in several ways. The main issue is that you should not use recursion. Since each element in the array only depends on elements with lesser indices, you can compute the values by a simple loop over the values of i and j.
I'm still not getting you. Lets say c = [1,3,5] and I get call a A[4][2] i.e. how many ways are there to represent 4 with coins {1, 3, 5}. But as c[2] > 4, hence A[4][2] = A[4][1] i.e. how many ways of representing 4 with coins 1,3 as it have coin 5.
Here is my final correct implementation paste.ofcode.org/PDQJbGzrFet2VXYBfMsQiq
|
2

While your implementation is a twist of the typical Coin Change Problem with 1 dimension less which may cause you double count a lot of the combinations, I think it is not that complicated for the given coin system.

I think the solution is simply floor(N/5) + 1

As you can only use [0..N/5] of 5 cents, other left over you must use 1 cents

This can be done that easily is because your coin system is canonical and greedy algorithm / mindset can be applied.

If you insist to use Dynamic Programming to solve the problem, you need to add one dimension, which represents which type of coins being used. This method is general with any coin systems

Define C(x, m):= The # of ways to make number x using first m type of coins

So now the recurrence formula become:

C(x, m) = C(x-coin_type[m], m) + C(x, m-1), means you choose to use the m-th type of coin, or not use it

Here is the main point, that why this recurrence works and yours not working, is the order of the iteration of the state.

Using this recurrence formula, we can do something like

For i = 0 to # of coin_type
    For j = 0 to n
       C(j, i) = C(j-coin_type[i], i) + C(j, i-1)

Notice the outer loop forces an ordering of iteration of the type of coins. Say coin_type = {1,3,5}, the loop will first count the way of using {1} only, then the next iteration of loop will count the way of using {1,3}, the last iteration will count the way using {1,3,5}.

You will never count the way using {3,1,5}, or {1,5,3}...etc. The order of the coin type is fixed, meaning you will not double count anything

Improve this answer

8 Comments

@Codor No, I did not minimize it, and OP 's question did not say it must be done using DP (and in fact it is greedy algorithm which is a special case of DP). Or can you provide an example that which partition do I miss?
Apparently, the approach given under the link in your answer is the correct solution. The recurrence relation in the original question is not correct.
@Codor Yes...and that's a general implementation for any coin system, while I think for the given one {1,5}, not even DP solution is needed...
Sadly, under the link, the semantics of C(N,m) is not given, but I believe it is the number of possiblities to represent an amount of N using only coins from (1,...,m).
@shole, of the obtained number of nickels and cents, I think the number of possible permutations with them is asked in question.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.