解可被3整除的硬币兑换问题(动态规划)

2024-09-29 03:23:27 发布

您现在位置:Python中文网/ 问答频道 /正文

我最近参加了一次工作面试,面试官让我调整硬币兑换问题,这样只会返回可被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整除。 面试官从未给过我答案,我开始怀疑这是否是一项不可能完成的任务


Tags: ofthe答案inforisvaluecount