动态规划 - 使用一组整数计算总和的方式数量

Question

我翻译的内容如下：

我浏览了这个问题：

求和为S且元素个数为N的所有方式 找到从给定集合中允许重复的数字中得出给定数字总和的所有方式

我没有很明白那里的回答，

我编写了两种解决问题的方法：

找到一些可以使用数字N（允许重复）达到总和S的方法数量

例如：总和=4和数字=1、2、3，答案是1111、22、1122、31、13、1212、2112、2212

我在其中一个方法中使用了记忆化，而在另一个方法中则没有。不知怎么地，在我的机器上，记忆化版本运行得比非记忆化版本慢得多。

这两种解决方案都有效。

记忆化版本：

def find_denomination_combinations(amount, denominations):
    memo = {}

    def calculate_combinations(max_amt):
        return_list = list()

        for denomination in denominations:
            new_sum = max_amt - denomination
            if new_sum == 0:
                return_list.append([max_amt])
                return return_list
            elif new_sum < 0:
                return [[]]
            else:
                if new_sum in memo:
                    combi_list = memo[new_sum]
                else:
                    combi_list = calculate_combinations(new_sum)
                for combination in combi_list:
                    if new_sum in memo and combination[:] not in memo[new_sum]:
                        memo[new_sum].append(combination[:])
                    else:
                        memo[new_sum] = []
                        memo[new_sum].append(combination[:])
                    combination.append(denomination)
                    return_list.append(combination)
        return return_list

    result = calculate_combinations(amount)
    return result

非记忆化版本

def find_denomination_combinations_nmemo(amount, denominations):

    def calculate_combinations(max_amt):
        return_list = list()

        for denomination in denominations:
            new_sum = max_amt - denomination
            if new_sum == 0:
                return_list.append([max_amt])
                return return_list
            elif new_sum < 0:
                return [[]]
            else:
                combi_list = calculate_combinations(new_sum)
                for combination in combi_list:
                    combination.append(denomination)
                    return_list.append(combination)
        return return_list

    result = calculate_combinations(amount)
    return result

我的算法是：

对于给定的整数集合中的每个D，计算[T(sum-D)]

如果输入的sum=16，整数集合为[1,2,3]

非记忆化版本运行时间为0.3秒，记忆化版本需要5秒

- jay

Answer 1

我认为记忆化版本较慢，因为它使用复杂的代码来更新最外层的else块中的记忆字典。这可以更简单：

if new_sum in memo:
    combi_list = memo[new_sum]
else:
    combi_list = memo[new_sum] = calculate_combinations(new_sum)
for combination in combi_list:
    return_list.append(combination + [denomination])

这样会快得多。有了这个修复，记忆化版本在大多数情况下应该比非记忆化代码更快。

然而还有其他问题。如果您的“denominations”列表未按递增顺序排序或存在面额值之间的间隙，则会得到错误的结果。基本上，任何可能导致触发“elif”情况的情况都将给出错误的结果。

以下是“for”循环主体的一个版本，可纠正这些问题：

new_sum = max_amt - denomination
if new_sum == 0:
    return_list.append([max_amt]) # don't return here, to allow unsorted denominations!
elif new_sum > 0:
    if new_sum in memo:
        combi_list = memo[new_sum]
    else:
        combi_list = memo[new_sum] = calculate_combinations(new_sum)
    for combination in combi_list:
        return_list.append(combination + [denomination])
# do nothing for new_amt < 0

你可以进一步简化事情，通过使每个调用将其自己的结果保存在memo字典中，而不是依赖其调用者来执行此操作，并通过将基本情况逻辑（对于new_sum == 0）与记忆化组合起来。我还重命名或删除了几个变量：

def find_denomination_combinations_blckknght(amount, denominations):
    memo = {0: [[]]} # prefill value for base case of calculate_combinations where amt==0

    def calculate_combinations(amt):
        if amt not in memo:
            memo[amt] = []
            for denomination in denominations:
                new_amt = amt - denomination
                if new_amt >= 0:
                    for combination in calculate_combinations(new_amt):
                        memo[amt].append(combination + [denomination])
                # do nothing for new_amt < 0
        return memo[amt]

    return calculate_combinations(amount)

这可能会稍微慢一些，可能是因为有额外的函数调用，但代码更简洁，没有任何elif或else情况！

- Blckknght

---

非常感谢！现在看起来干净多了！我也是这么想的，我这里没有做太多的计算，只是设置和获取，如果这可能导致速度变慢。确实如此！ - jay