解説をよんで最初分からなかった部分が腹落ちしたので書いておく。
疑問に感じたのは、途中で使ったボールの操作を打ち消すのに、最新の状態のDPテーブルへの操作で良い理由。
合計K以上のDPテーブルを持たなくて良い理由の部分。
の2点。
直感的にはボールが減るときにK以上の和からの遷移が発生するのでは？と感じていた。
ボールの集合の和sの場合の数のDPの遷移は、ボールに書かれた数をaとして、
dp[s]+=dp[s-a]
このとき最後に使ったボールを削除するのは、この操作を打ち消せば良くて、
dp[s]-=dp[s-a]
このDPを考えるとき、ボールの集合の計算する順番が違っても結果は変わらないので、任意のボールの操作を打ち消すとき、打ち消すボールを最後に計算したことにして、考えても問題ない。
よって1番目の疑問は解消した。
同時に遷移の式をみればK以上のDPテーブルを保持する必要がないこともわかる。
