取り敢えず，解いた．

しかし，少し遅い．約20秒 (Core 2 Duo E8500).

もうすこし工夫して下限を求めるか，

探索方法を工夫するか，

の二択なのか？

追記 #1

ad hoc な工夫をして，約3秒になった．

しかし，もう少し綺麗な改良の方法はないのか？

追記 #2

C++ で配列使ったアルゴリズムで実装したら，約0.2秒になった．

計算結果の再利用をしまくって，かなり速くなった．

教訓

配列のサイズが大きすぎると，スタックにのらずに，セグフォになるらしい．

そういときは，newで動的に確保するべし，ってどっかで読んだ．

例えば，二次元配列の場合 

int (* a)[10] = new int[N][10];

とすれば，動的に確保できるらしい．