Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: Number of Ways to Represent N Dollars

Solution Review: Number of Ways to Represent N Dollars

In this lesson, we will see some solutions to the problem from the last challenge.

We'll cover the following...

Solution 1: Simple recursion

Press + to interact
def countways_(bills, amount, maximum):
  if amount == 0:     # base case 1
    return 1
  ways = 0
  # iterate over bills
  for bill in bills:    
    # to avoid repetition of similar sequences, use bills smaller than maximum
    if bill <= maximum and amount - bill >= 0:  
      # notice how bill becomes maximum in recursive call    
      ways += countways_(bills, amount-bill, bill)  
  return ways
def countways(bills, amount):
  return countways_(bills, amount, max(bills))
print(countways([1,2,5], 5))
Note: Increased size of the inputs (more elements in the bill list) and the bigger the value of the amount might raise an error in the case of recursion due to stack overflow or you may get Execution Timed Out!.

Explanation

Finding different combinations in a set of things is not difficult at all. In fact, one of the first problems we did in this course was finding different permutations of a string. A slightly challenging bit was how to avoid overcounting due to the same permutations. For example, $10 + $20 adds to $30, so does $20 + $10. In the context of permutations, both these sequences would be distinct, but in the case of combinations, these are the same, meaning we must not count them twice. We achieve this by restricting each recursive call to use a subset of bills. The first call can use all n bills, the second call can use n-1 bills excluding the largest one (lines 8-10), and so on. This way it is not possible that a recursive call that used a smaller bill would select a larger bill in later recursive calls; thereby avoiding the scenario of cases like $10 + $20. Notice that as a base case, we return 1 when amount is zero because there is only one way to represent zero irrespective of the number and kinds of bills available. Look at the following visualization of the algorithm.

Another plausible recursive solution is given in the following coding playground. The logic is similar to the first solution, but it is simpler.

Alternate algorithm

Press + to interact
def countways_(bills, amount, index):
  if amount == 0:     # base case 1
    return 1
  if amount < 0 or index >= len(bills):      # base case 2
    return 0
  # count the number of ways to make amount by including bills[index] and excluding bills[index]
  return countways_(bills, amount - bills[index], index) + countways_(bills, amount, index+1)
def countways(bills, amount):
  return countways_(bills, amount, 0)
print(countways([1,2,5], 5))

Explanation

The key part of this solution is the sum of two recursive calls in line 7. To count to amount, some combinations will either include a specific bill given by bills[index] or they won’t. So, we can simply count both these possibilities. The first call to countways_ counts bills[index] as a part of the solution, whereas the second call skips over it. Let’s see a simple visualization of this algorithm.

Time complexity

If the length of the list bills is n, and the amount to be ...