python-3.x - 使用记忆化的硬币找零问题（亚马逊面试问题）

Question

def rec_coin_dynam(target,coins,known_results):
    '''
    INPUT: This funciton takes in a target amount and a list of possible coins to use.
    It also takes a third parameter, known_results, indicating previously calculated results.
    The known_results parameter shoud be started with [0] * (target+1)
    
    OUTPUT: Minimum number of coins needed to make the target.
    '''
    
    # Default output to target
    min_coins = target
    
    # Base Case
    if target in coins:
        known_results[target] = 1
        return 1
    
    # Return a known result if it happens to be greater than 1
    elif known_results[target] > 0:
        return known_results[target]
    
    else:
        # for every coin value that is <= than target
        for i in [c for c in coins if c <= target]:
            
            # Recursive call, note how we include the known results!
            num_coins = 1 + rec_coin_dynam(target-i,coins,known_results)
            
            # Reset Minimum if we have a new minimum
            if num_coins < min_coins:
                min_coins = num_coins
                
                # Reset the known result
                known_results[target] = min_coins
                
    return min_coins

这运行得很好，但我对此几乎没有疑问。

我们给它以下输入来运行：

target = 74
coins = [1,5,10,25]
known_results = [0]*(target+1)
rec_coin_dynam(target,coins,known_results)

为什么我们用长度目标 + 1 的零来初始化已知结果？为什么我们不能写

know_results = []

标签： python-3.xrecursionmemoization

Answer 1

请注意，代码包含以下行：

known_results[target] = 1
return known_results[target]
known_results[target] = min_coins

现在，让我演示一下python交互式shell[]之间的区别：[0]*something

>>> a = []
>>> b = [0]*10
>>> a
[]
>>> b
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>>
>>> a[3] = 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list assignment index out of range
>>>
>>> b[3] = 1
>>>
>>> a
[]
>>> b
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]

引发异常IndexError: list assignment index out of range是因为我们尝试访问 list 的单元格 3 a，但a大小为 0；没有单元格 3。我们可以在ausing中输入一个值a.append(1)，但是 1 将位于位置 0，而不是位置 3。

当我们访问 list 的单元格 3 时也不例外b，因为b大小为 10，所以 0 到 9 之间的任何索引都是有效的。

结论：如果你事先知道你的数组的大小，并且这个大小在算法执行期间永远不会改变，那么你最好从一个适当大小的数组开始，而不是从一个空数组开始。

的大小是known_results多少？该算法需要从0到的值的结果target。那是多少个结果？正是target+1。例如，如果target = 2，那么算法将处理 0、1 和 2 的结果；这是 3 个不同的结果。因此known_results必须有大小target+1。请注意，在 python 中，就像在几乎所有其他编程语言中一样，大小为 n 的列表有 n 个元素，索引为 0 到 n-1。一般来说，在一个整数区间[a, b]中，有b-a+1个整数。例如，区间 [8, 10] 中有三个整数（分别是 8、9 和 10）。