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

Question

我看过这个问题：

用N个数字加起来得到一个和S的方式有多少种 从给定的集合中找出所有可以加到指定数字的方式（允许重复）

不过我对那里的答案不是很理解，

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

找出用数字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

我的算法是：

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

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

不记忆化版本运行了0.3秒，而记忆化版本却需要5秒。

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

不过你还可以进一步简化，让每次调用自己把结果保存在记忆字典中，而不是依赖调用者来做，并且把基本情况的逻辑（对于 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 的情况！