时间戳

首页 > 解决方案 > 加权字符串的组合：用 sum(integers) = m 计算整数组合的数量

python - 加权字符串的组合：用 sum(integers) = m 计算整数组合的数量

问题描述

给定一个整数列表，例如

l = [3, 5, 8, 13]

和一个整数，例如

m = 13

计算 sum=m 的整数组合的数量，例如

combinations = len([[8, 5], [5, 8], [13], [3, 5, 5], [5, 5, 3], [3, 5, 3], ...])

对于较小的 m 值，我可以使用这种递归（类似斐波那契的线性递归关系）：

def RecursiveCount(m, integers):
    count = 0
    if m < 0:
        return 0
    if m == 0:
        return 1
    for i in integers:
        count += RecursiveCount(m-i, integers)
    return count

但是对于较大的 l 和 m，它会变慢，并且建议使用动态编程来记忆已经解决的组合以减少递归调用。不幸的是，我无法实现这一点。我尝试阅读此内容，但没有帮助https://bio.informatik.uni-jena.de/wp/wp-content/uploads/2014/09/book_handout_3.pdf

编辑：学习成果将是最好的，如果我能够使用动态编程来实现它

标签： pythondynamic-programming

解决方案

@functools.lru_cache您可以通过将装饰器添加到递归函数来轻松添加记忆。

@functools.lru_cache()
def RecursiveCount(m, integers):
    ...

这将自动缓存某些参数的结果，并在再次调用该函数之前先检查该缓存，从而显着减少调用次数，从而减少运行时间。但是，这要求所有参数都是可散列的，即您必须integers作为tuple.

示例RecursiveCount(20, tuple(range(1, 10))))：结果：518,145；没有记忆的函数调用：4,672,513；带记忆：29。

（如果这是用于 DP 的练习，这可能不是一个选项，但否则这在实践中效果很好。）

推荐阅读