1

来自 codewars 的问题https://www.codewars.com/kata/52ec24228a515e620b0005ef/python

在数论和组合学中，正整数 n 的分区，也称为整数分区，是一种将 n 写为正整数之和的方式。仅在其被加数的顺序上不同的两个和被认为是相同的分区。如果顺序很重要，那么总和就变成了一个组合。例如，4 可以以五种不同的方式进行分区：

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

给定数字 n，编写一个函数 exp_sum(n)，它返回 n 可以划分的方式总数。例如：exp_sum(4) = 5

为什么递归方法：

def exp_sum(n):
    arr = list(range(1, n+1))
    mem = {}
    return rec(n, arr, mem)


def rec(n, arr, mem):
    key = str(n)+ ":" + str(arr)
    if key in mem:
        return mem[key]
    elif n < 0:
        return 0

    elif n == 0:
        return 1

    elif n > 0 and not arr:
        return 0

    else:
        to_return = rec(n - arr[-1], arr, mem) + rec(n, arr[:-1], mem)

    mem[key] = to_return
    return to_return

与此特定方法（此 kata 的最佳解决方案）相比，运行时间要长得多？

def exp_sum(n):
  if n < 0:
    return 0
  dp = [1]+[0]*n
  for num in range(1,n+1):
    for i in range(num,n+1):
      dp[i] += dp[i-num]
  return dp[-1]

即使使用记忆化，递归方法也几乎无法在大约 10000 毫秒的时间内通过测试用例，而上述方法需要 1000 毫秒。

谁能解释上面的特定方法是如何工作的以及它背后的逻辑，或者它是否使用了一些我可以阅读的特定算法？

4

0 回答 0