Coin Change problem using Memoization（亚马逊面试题）

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)

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

know_results = []

Answer 1

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

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

现在，让我来演示 python 交互中 [] 和 [0]*something 的区别 shell:

>>> 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 是因为我们试图访问列表 a 的单元格 3，但 a 的大小为 0；没有单元格 3。我们可以使用 a.append(1) 在 a 中放置一个值，但是 1 将位于位置 0，而不是位置 3。

当我们访问列表 b 的单元格 3 时没有异常，因为 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）。

Coin Change problem using Memoization（亚马逊面试题）

Coin Change problem using Memoization (Amazon interview question)

python-3.x

recursion

memoization