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

Question

我回答了这个问题

Number of ways to add up to a sum S with N numbers Find all ways to sum given number (with repetitions allowed) from given set

不太明白那里的答案，

我写了两个方法来解决一个问题:

使用数字 N 求和 S 的方法数(允许重复)

例如。 sum = 4 and numbers = 1,2,3 答案是 1111, 22, 1122, 31, 13, 1212, 2112, 2212

在一种方法中我使用内存，而在另一种方法中我不使用。不知何故，在我的机器上，memoize 版本比非 memoized 版本运行得慢

这两种解决方案都有效。

内存版本:

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

我的算法是:

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

如果输入总和 = 16 且整数集 = [1,2,3]

非内存版本运行时间为 0.3 秒，内存版本需要 5 秒

Answer 1

我相信 memoized 版本比较慢，因为它使用复杂的代码来更新最外层 else block 中的 memo dict。它可以简单得多:

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

不过，您可以进一步简化事情，方法是让每个调用都将自己的结果保存在备忘录字典中，而不是依赖调用者这样做，并结合基本情况逻辑(对于 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 情况!