python - 再帰またはその他の方法を使用して数値の合計 (整数パーティション) を取得する方法の数

Question

コードウォーズからの質問https://www.codewars.com/kata/52ec24228a515e620b0005ef/python

整数論と組み合わせ論では、整数分割とも呼ばれる正の整数 n の分割は、正の整数の和として n を記述する方法です。被加数の順序のみが異なる 2 つの合計は、同じパーティションと見なされます。順序が重要な場合、合計は合成になります。たとえば、4 は 5 つの異なる方法で分割できます。

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

数 n を指定して、n を分割できる方法の総数を返す関数 exp_sum(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

この特定の方法（このカタのトップソリューション）と比較して、実行に時間がかかりますか？

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]

メモ化を使用しても、再帰アプローチは、上記のアプローチで 1000 ミリ秒かかるのに比べて、約 10000 ミリ秒でテスト ケースをほとんど通過できませんでした。

そして、上記の特定の方法がどのように機能するか、その背後にあるロジック、または私が読むことができる特定のアルゴリズムを使用しているかどうかを誰かが説明できますか?