分割数

問題（分割数）

$ n $ 個の品物を、$ m $ 個以下に分割する方法の総数を求めて下さい。

解き方・ソースコード

n の m 分割 $ a_i ( \sum_{i=1}^{m}a_i=n ) $ を考えてみます。

全ての $ i $ で $ a_i > 0 $ ならば、$ {a_i - 1} $ は $ n - m $ の $ m $ 分割となります。

また、$ a_i = 0 $ となる $ i $ が存在したら、これは $ n $ の $ m - 1 $ 分割となります。

したがって、次のような漸化式を立てることができます。

$$ dp[i][j] = dp[i][j - i] + dp[i - 1][j] $$

この漸化式ならば重複なく分割数を数え上げることができ、計算量は $ 0(mn) $ となります。

[Google Colaboratory]

#--------- 入力例 -----------
n = 4   # 品物の数
m = 3   # 分割数
#----------------------------
memo = {(0,0): 1}

for i in range(1, m + 1):       # 分割数に対応するループ
    for j in range(n + 1):      # 品物の数に対応するループ
        if j - i >= 0:
            memo[i, j] = memo.get((i - 1, j), 0) + memo.get((i, j - i), 0)
        else:
            memo[i, j] = memo[i - 1, j]
print('解：', memo[m, n])

[実行結果]

解： 4

4個の品物を3分割以下にする方法は、[1 1 2]、[1 3]、[2 2]、[4]の４パターンあるので、解は4となります。