2011JOI予選D 1年生 解説

問題リンク

解説

基本的な動的計画法（DP）の問題です。

式の 項目までで、値が になるような式の個数を として遷移していきます。 遷移式は簡単なので自分で考えてみましょう。

このような数え上げDPでは、「同一視できる状態をすべてうまく同一視する」という考え方が重要です。 今回だと、同じ場所までの式で値が同じになっていれば、そこまでの式の形がどうなっていたとしてもそれ以降に影響を及ぼしません。 よって、同一視することができ、計算量を削減できます。

DPは、式を立てるまでの慣れが重要です。 JOIの過去問でDPに積極的に触れて、DPの問題に出会ったときにすぐに解けるようにしましょう。