Y箱

100を自然数の和に分割する問題です。

初めは動的計画法のつもりで、1から積み上げていく方法をやってみたのですが、あえなく時間切れ。

Wikipediaでこれが自然数の分割というのだということを知り、とりあえずそこに出ていた式を実装してみたら解けた。







漸化式はこれ

• p(k, n) = 0 if k > n

• p(k, n) = 1 if k = n

• p(k, n) = p(k+1, n) + p(k, n − k) otherwise.

と言っても、メモ化してるので、動的計画法には違いない。




- partition-num
Wikipediaの漸化式をそのまま関数にしただけ。 自前のdefn-memoでメモ化している。
clojureのmemoizeは、1.3になっても再帰の中の関数呼び出しには効果が無いようなので、使えません。
また、末尾再帰にもなっていませんが、たかだか100段程度なので、スタックはあふれません。

(partition-num 1 100) とすると答えが出ます。