我最近参加了一次工作面试,面试官让我调整硬币兑换问题,这样只会返回可被3整除的答案
这个问题必须用动态规划的方法来解决换硬币的问题,我有点卡住了。我已经用一个生成器解决了这个问题,但对于较大的数字来说,这太慢了
很明显,要检查一个数字是否可以被三整除
number%3==0
然后从https://www.geeksforgeeks.org/coin-change-dp-7/给出这个模板
# Dynamic Programming Python implementation of Coin
# Change problem
def count(S, m, n):
# table[i] will be storing the number of solutions for
# value i. We need n+1 rows as the table is constructed
# in bottom up manner using the base case (n = 0)
# Initialize all table values as 0
table = [0 for k in range(n+1)]
# Base case (If given value is 0)
table[0] = 1
# Pick all coins one by one and update the table[] values
# after the index greater than or equal to the value of the
# picked coin
for i in range(0,m):
for j in range(S[i],n+1):
table[j] += table[j-S[i]]
return table[n]
# Driver program to test above function
arr = [50, 20, 10,1] # list of coins
m = len(arr)
n = 10000 # amount
x = count(arr, m, n)
print (x)
# This code is contributed by Afzal Ansari
我不明白如何得到解的数量,并使用if来保持解可以被3整除。 面试官从未给过我答案,我开始怀疑这是否是一项不可能完成的任务
目前没有回答
相关问题 更多 >
编程相关推荐