python の整数分割問題の解き方

Pythonの整数分割問題を解くには、動的計画法を用いることができます。

まず、integer_partition(n)関数を定義します。ここで、nは分割される整数を表します。計算結果を保存するリストdpを使用できます。dp[i]は、分割される整数がiのときの分割スキーム数を表します。

dpのリストをすべて0で初期化し、dp[0]を1にします。

それでは、dp[i] の値を小さいものから計算していきます。各iに対して、iを異なる整数の集合に分割する可能な分割方法をすべて試行します。分割された整数をjとします。

iをjとi-jに分割でき、i-jをさらに分割できる。

よって、漸化式として dp[i] = dp[i] + dp[i-j] が得られる。

最後に、dp[n]を整数分割の結果として返す。

動的計画法を用いて整数分割問題を解くPythonコード例を以下に示します。

def integer_partition(n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] += dp[i - j]
return dp[n]

本関数を利用する時、例えばinteger_partition(5)とすると7が返り、5を自然数に分割する方法の数が7通りであることを意味します。