0

This is a dynamic programming solution to the minimum change problem in python from Bryce Boe. I don't understand what's going on in the elif block in general. More specifically, what is the [:] doing in this line 

table[i] = table[i - coin][:]

Could this be written with a dictionary instead of the table memoization list? 

def solve_coin_change(coins, value):
    """A dynamic solution to the coin change problem"""

    table = [None for x in range(value + 1)]
    table[0] = []
    for i in range(1, value + 1):
        for coin in coins:
            if coin > i:
                continue
            elif not table[i] or len(table[i - coin]) + 1 < len(table[i]):
                if table[i - coin] != None:
                    table[i] = table[i - coin][:]
                    table[i].append(coin)

    if table[-1] != None:
        print('%d coins: %s' % (len(table[-1]), table[-1]))
    else:
        print('No solution possible')

coins = [1, 2, 4]
value = 11

solve_coin_change(coins, value)
Oblio
  • 39
  • 4

2 Answers2

3

This line is making a copy of the list table[i - coin], not an alias. It is using slice notation.

table[i] = table[i - coin][:]

Each element is copied, instead of assigning a new label to table[i - coin], making table[i] an independent object; i/e if you can modify either table[i - coin], or table[i] independently of the other.

Reblochon Masque
  • 35,405
  • 10
  • 55
  • 80
2

That is the list slicing notation. In this case it is being used to make a copy of table[i - coin], instead of using a reference.

user3808852
  • 33
  • 5