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

Question

我问了这个问题

求和的方法数S与N个数求和的所有方法从给定集合中求和给定数（允许重复）

不太明白那里的答案，

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

用数字N（允许重复）找出求和S的方法数

sum=4，number=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

我的算法是：

[T（sum-D）]，其中D属于给定的整数集

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

非备忘录版本运行0.3秒，备忘录版本需要5秒

Answer 1

我相信备忘录化版本较慢，因为它使用复杂的代码来更新最外层ore块中的备忘录判决。它可以简单得多：

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])

这要快得多。有了这个修复，在大多数情况下，备忘录化版本应该比非备忘录化代码更快。

不过，还有其他问题。如果您的面额列表没有按递增顺序排序，或者面额值之间存在间隙，则会得到错误的结果。基本上，任何可能导致elif案例被命中的情况都会给出错误的结果。

以下是用于纠正这些问题的循环体的版本：

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

不过，您可以进一步简化事情，方法是让每个调用在备忘录中保存自己的结果，而不是依赖其调用者这样做，并将基本案例逻辑（fornew_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案例！