Quiz: Dynamic Programming

Congrats! You made it to the last quiz!

1

Which is the correct algorithm for the Money Change Problem?

A)
def change(money):
table = [float('inf')] * (money + 1)
table[0] = 0

for m in range(1, money + 1):
for coin in (1, 3, 4):
if coin <= m:
table[m] = min(table[m], table[m - coin])
return table[money]

B)
def change(money):
table = [float('inf')] * (money + 1)
table[0] = 0

for m in range(1, money + 1):
for coin in (1, 3, 4):
if coin <= m:
table[m] = min(table[m], table[m - coin] + 1)
return table[money]

C)
def change(money):
table = [float('inf')] * (money + 1)
table[0] = 0

for m in range(1, money + 1):
for coin in (1, 3, 4):
if coin <= m:
table[m] = max(table[m], table[m - coin] + 1)
return table[money]

D)
def change(money):
table = [float('inf')] * (money + 1)
table[0] = 0

for m in range(1, money + 1):
for coin in (1, 3, 4):
if coin <= m:
table[m] = min(table[m], table[coin] + 1)
return table[money]

Question 1 of 60 attempted

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.