arrays - 面额为6的快速更改算法:面试练习

我找到了解决这个问题的办法，但需要O（n^2）。有可能做得更好吗？
问题：假设我们想兑换D美元。我们有一个包含N个元素的数组A数组中的面值作为美元值存在，但我们不知道高级的确切面额。但是，我们得到的是0前任：
如果a=[3,4,6,5,20,18,10,30]且d=50。然后该算法返回自5+5+5+5+10+20以来的真值。
我的尝试：
我试过先排序，然后再划分，但后来我被卡住了，因为我不知道如何消除可能的选择，因为我不知道数组中到底是什么。更好的是，如果不在O（n^2）时间内明确地通过，我不确定如何确定地说这是不可能的有没有可能利用这样一个事实：我知道我只限于6张钞票？

最佳答案

在我看来这是一个典型的递归问题让我们编写一个函数来检查我们是否可以更改D美元。为此，我们将取第一张账单（假设是3美元），从D中删除它，然后递归地检查我们是否可以更改D - 3美元。
如果我们不检查已经检查过的组合，我们可以使这个解决方案更快因此，如果我们已经知道账单不符合我们的需求，那么我们也不需要检查组合。为此，我们需要首先对3, 5, 10数组进行排序，然后将上次使用的票据数（5, 10, 3）传递给A函数。在函数内部，我们不需要检查数字小于last_bill_id的票据的任何组合。
python的完整解决方案：

A = [3, 4, 6, 5, 20, 18, 10, 30]
D = 50


def check(counters, current_sum, depth, last_bill_id):
    global A
    if depth > 6:  # max amount of bills is 6
        return False
    if depth == 6:  # we used 6 bill, did we get the correct sum?
        return current_sum == 0
    if current_sum <= 0:  # we gave too much change
        return False
    # current_sum > 0 and depth < 6
    for i in xrange(last_bill_id, len(A)):
        if counters[i] < 6:
            # we can use i-th bill another time
            counters[i] += 1
            if check(counters, current_sum - A[i], depth + 1, i):
                return True
            counters[i] -= 1
    return False


# init counters with zeros
counters = [0] * len(A)
# check if we can change for `D`
A = sorted(A)  # sort A before the function
print 'Can make change:', check(counters, D, 0, 0)
# print bills with counters
for i, c in enumerate(counters):
    if c > 0:
        print '$%d x %d' % (A[i], c)

输出：
能改变：真的
3美元x 4美元
18美元x 1
20美元x 1
编辑
以前的解决方案具有复杂性check。但实际上，我们可以用memoization（或者用另一种方式说，dynamic programming）使它更快。让我们对last_bill_id数组进行排序，并重复其中的每个数字6次，这样我们将得到类似O(n^6)的结果。现在让我们填充3d矩阵A，其中A = [3, 3, 3, 3, 3, 3, 5, 5, ...]是M[,,]如果我们可以使用M[bills_num, i, d]票据对true美元进行更改，从d数组的第bills_num位置开始。结果将显示在单元格中这个矩阵的大小是i，所以我们可以用A时间来填充它（使用与前面的解类似的递归方法）。python中的代码：

A = [3, 4, 6, 5, 20, 18, 10, 30]
D = 50

# sort A and repeat 6 times
A = sorted(A * 6)
# create matrix M, where:
# 0 == uncomputed, 1 == True, -1 == False
arr1d = lambda x: [0] * x
arr2d = lambda x, y: [arr1d(y) for i in xrange(x)]
arr3d = lambda x, y, z: [arr2d(y, z) for i in xrange(x)]
M = arr3d(6 + 1, len(A), D + 1)


def fill_m(bills_num, start_pos, d):
    global A, M
    if d == 0:  # can make change for 0 only with 0 bills
        return True if bills_num == 0 else False
    if d < 0 or bills_num <= 0 or start_pos >= len(A):
        return False
    if M[bills_num][start_pos][d] == 0:
        # need to compute cell value
        if fill_m(bills_num, start_pos + 1, d):
            M[bills_num][start_pos][d] = 1
        elif fill_m(bills_num - 1, start_pos + 1, d - A[start_pos]):
            M[bills_num][start_pos][d] = 1
        else:
            M[bills_num][start_pos][d] = -1
    return M[bills_num][start_pos][d] == 1


print 'Can make change for $', D, fill_m(6, 0, D)