「自信なし」と書きましたが，「確信」に変わりました．

ある自然数 T について，答えが T 以下であるか否かを判定するのにかかる
時間は O(n)．２分探索を行うならば，答えが T 以下になるかどうかの判定を
O(log σ) 回のを行えばよい（ただし，σ = i_1 + i_2 + ... + i_n）．
よって，全体の計算量は O(n log σ)．

i_1, ... , i_n として，桁数が kn より大きい数を扱うことは通常はないと
思われるので，O(n log σ) は，O(kn^2) より十分速いと思われる．

なお，２分探索による解法の時間計算量を調べる際，上界に σ，下界に 0 という
自明な値を用いたが，自明でない上界，下界を使えば，実際はもっと速いだろう．

結論：
>>1 の問題は動的計画法の例題としては良くできている．
でも，この問題を解くのに本当に動的計画法を使うべきではない．