给定一个整数列表，例如
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
编辑:学习成果将是最大的，如果我能够使用动态规划来实现它
请您参考如下方法:
您可以通过添加 @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 的练习，这可能不是一个选项，但在实践中这很有效。)
