Updated on 

分割数

分割数とは

自然数を 以上の整数に分割する場合の数
で表す

パターン

  • 「 個の 以上の整数への分割」→ 通り
  • 「任意の個数の 以上の整数への分割」→ 通り

計算量

漸化式

導出


(を個の以上の整数に分割する場合の数)
(を個の以上の整数に分割する場合の数)

  1. を含むもの
    つのを取り除き、残りの個を以上の和で表す方法をを調べれば良い→ 通り
  2. を含まないもの
    を以上の整数個に分割する場合の数→ 通り

実装

1
def init_array(i, j, val=0): return [[val]*j for _ in range(i)]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
N, K = 5, 3
dp = init_array(N+1, K+1, 0)
dp[0][0] = 1

for n in range(N+1):
    for k in range(1, K+1):
        if n - k >= 0:
            dp[n][k] = dp[n][k-1] + dp[n-k][k]
        else:
            dp[n][k] = dp[n][k-1]

print(*dp, sep="\n")
print(dp[N][K])

# ---- out -----
# 5
# 5 = 5+0+0
#   = 4+1+0
#   = 3+2+0
#   = 3+1+1
#   = 2+2+1

このページはHexoとStellarを使用して作成されました。