読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

Naive DP Implementation of Integer Partition Function with the Complexity O(N^3)

整数を分割したい病に患ってしまった。見る整数はなんでも、4=1+1+1+1=1+1+2=1+3=2+2のように分割してしまう恐ろしい病気だ。ちなみに4の場合の分割数は5である(自身も含める)。Wikipedia(https://en.wikipedia.org/wiki/Partition_(number_theory) )を読んでいた所、この数を計算するアルゴリズムとして次のようなものが載っていた:

補助関数 p(n,m)をm以下の数の和でnを表現する場合の数とするとp(n,n)が求めるもので、p(0,i)=1、p(i,j)=p(i,i) where i

これをそのままコードに落とすとO(N^3)でとても遅い。遅いアルゴリズムは泣きたくなる。

#!ruby
M=1000000007
def integer_partition_naive(n)
	dp=Array.new(n+1){Array.new(n+1,0)}
	dp[0][0]=1
	1.upto(n){|k|dp[0][k]=1}

	1.upto(n){|i|
		1.upto(n){|k|
			if k>i
				dp[i][k]=dp[i][i]
				next
			end
			1.upto(k){|j|
				dp[i][k]=(dp[i][k]+dp[i-j][j])%M
			}
		}
	}
	dp[n][n]
end