本履歴

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

Faster DP Implementation of Integer Partition Function with the Complexity O(N^2)

そこで色々調べた所、蟻本にO(N^2)の方法が載っている事がわかって一件落着。こちらもDPだけど、分割する数を取るのが違う点。

DP[n,m]=nをm個以下で分割するときの総数とするとDP[n,m]=DP[n,m-1]+DP[n-m,m]

nをm個以下の整数の和にするときに0も含めて考えているのがナルホド。そして、0を含むものと含まないもので分けて、うまく次元が低い処理にそれぞれ帰着できているのがすごい(小並感)

#!ruby
M=1000000007
def integer_partition_faster(n)
	dp=Array.new(n+1){Array.new(n+1,0)}
	dp[0][0]=1
	1.upto(n){|j|
		0.upto(n){|i|
			if i-j>=0
				dp[i][j]=(dp[i][j-1]+dp[i-j][j])%M
			else
				dp[i][j]=dp[i][j-1]
			end
		}
	}
	dp[n][n]
end

さて、実際の両者のコードをよく眺めると、結構似てる気がしませんか? 意図的に添字を同じにしたのもあるけど。というわけで、両アルゴリズムで使われている変数のdpを比べてみるとなんと驚き(ドラムロールオン♪)、中身が全く一緒になっているじゃありませんか!! Curiouser and curiouser. Don't you think so?

整数の分割って数論の一分野になっていますが、実は面白い定理が成り立つのです:

整数 n を分割したときの成分の数が k 個以下になるような分割の総数は、成分が k 以下の整数となるような n の分割の総数に等しい。

はい、そのまんまですね(笑)。なんか競プロの練習を通じてこの定理を証明したっぽい感じがしましたので、熱が冷めないうちにblog記事にしてみました。
その名もズバリ整数の分割って本に証明とかヤング図形との対応とかその他諸々興味深いことが詳しく載ってたはず。

整数の分割

整数の分割