SRM 649 DIV2 Mid

問題

自然数NとKが入力される(どちらも100以下)
最初、集合AをA={N}とする。
何度かのステップでAの要素を全て0にしたい。一つのステップでは、Aの要素全てに対して、それぞれに1と2のどちらかを適用することが出来る。
1.その要素akをAから削除した後、akを二つの和に分割してAに追加する。
つまり、A -> A-{ak}+{i,ak-i}(1<=i<=ak-1)
2.akの値を1減らす
また、制約として1.の操作は全部で2回しか行うことが出来ない。

(最終的なAの要素数はいくらになっても構わない)
最小ステップ数はいくらか。

Sample Input

N=5,K=2の場合
{5} -> {2,3} (1の操作) -> {1,2} (2の操作) -> {1,1}(1の操作を1に,2の操作を2に) -> {0,0}

N=15,K=4の場合
{15} -> {7,8} (1の操作) -> {3,4,4,4} (2の操作を2回適用) -> {2,2,2,3,3} (1の操作は残り1回しか適用できないので一つの4に適用してあとは1の操作) -> {0,0,0,0,0}(1の操作を3回)
の合計6ステップ。

解法

f(n,k) = {n}をk回の分割が許容された状態における最小ステップ数
とおいてDP.