如何正确实现memoization？

Question

我在编程挑战上花费了太多的时间：

给定一个预算和一组价格，计算所有关于如何花费整个预算的独特组合。

示例

输入

budget = 100
prices = [25, 50]

输出

[[25, 25, 25, 25], [25, 25, 50], [25, 50, 25], [50, 25, 25], [50, 50]]

我已经用Python实现了一个可以正常工作的暴力解决方案：

def spend_the_budget(budget: int, prices: list) -> list:
    if budget == 0:
        return [[]]
    if budget < 0:
        return None

    combinations = []
    for price in prices:
        remainder = budget - price
        remainder_combinations = spend_the_budget(remainder, prices)
        if remainder_combinations is not None:
            for remainder_combination in remainder_combinations:
                remainder_combination += [price]
                combinations.append(remainder_combination)
    return combinations

然而，这具有明显的指数时间复杂度，因此不能以可接受的方式进行扩展。因此，我想添加memoization，但似乎无法使其工作：

def spend_the_budget_memoized(budget: int, prices: list, memo: dict = {}) -> list:
    if budget in memo:
        return memo[budget]
    if budget == 0:
        return [[]]
    if budget < 0:
        return None

    combinations = []
    for price in prices:
        remainder = budget - price
        remainder_combinations = spend_the_budget_memoized(remainder, prices, memo)
        if remainder_combinations is not None:
            for remainder_combination in remainder_combinations:
                remainder_combination += [price]
                combinations.append(remainder_combination)
    memo[budget] = combinations
    return combinations

然而，奇怪的是，这会产生一个不正确的结果，我不能纠结于我在这里做错了什么：

输出

[[25, 25, 25, 50, 25, 25, 50], [50, 25, 25, 50], [25, 25, 25, 50, 25, 25, 50], [25, 25, 25, 50, 25, 25, 50], [50, 25, 25, 50]]

Answer 1

for remainder_combination in remainder_combinations:
                remainder_combination += [price]
                combinations.append(remainder_combination)

当您遍历remainder_combinations时，您就是在遍历存储在memo中的同一副本。改用list.copy()，

for remainder_combination in remainder_combinations:
                temp = remainder_combination.copy()
                temp += [price]
                combinations.append(temp)