問題概要

問題文はこちらを参照してください。

AtCoderのTypical DP ContestはＤＰの練習にお勧めです。難しい問題が多いですが、理解してみると典型的なＤＰ問題が多く含まれています。今だに全部は解けていませんけど。。。

解法

$i-1$問目までの問題からできる合計点の集合がわかれば、それに$i$問目の配点$p_{i}$を足してできる合計点と、足さずにできる合計点を考えることで、$i$問目までの問題からできる合計点の集合がわかります。この時、合計点が同じであればどの問題の組み合わせによって出来た点数なのかが関係なくなっているため、解くべき部分問題を減らすことができています。

このままコーディングに入っても構わないんですけど、漸化式をちゃんと考えないとうまくできないことが多いので、定義してみます。

漸化式の定義： $$dp[i][j]=\begin{cases} dp[i-1][j]\lor dp[i-1][j-p_i] & (j\ge p_i) \\ dp[i-1][j] & (j\lt p_i) \end{cases}$$

$dp[i][j]$：$i$問目までの問題を使って、$j$点の合計点ができるかどうかの真理値
$(0\le i \le n,\ 0\le j \le MAX,\ $ $MAX$：合計点として考えられる最大値$\displaystyle \sum_{i} p_i)$

初期値：$dp[0][0]=1$

求める解：$dp[n][j]$が$1$となる要素数

ここではいわゆる「貰うＤＰ」で、$i$のループは$1$から$n$に増える方向で漸化式を考えましたが、配るＤＰや、$i$のループが逆でも考えることができます。この辺の、同じＤＰでもいろいろな解法があるのことが、なかなか直感的にＤＰの問題が解けない1つの要因かなと思ったりしています。

ちなみに、この漸化式だと$j$のループを$MAX$から減る方向に回すことで、配列は1次元で済みます。こういう事を考え出すとますます難しくなる。。。

考察

動的計画法は次の2つの特徴がある場合に適用できます。

  1. 問題が、その問題よりも小さい部分問題を用いて解くことができる（部分構造最適性）
  2. 同じ部分問題を繰り返し解く（部分問題重複性）

この問題でいえば、

  1. $i$問目までの答えが、$i-1$問目までの答えから得られる。
  2. 合計点が$j$点と同じであれば、どの問題の組み合わせによる合計点かにかかわらず答えは同じなので、$2^N$の組み合わせが、合計点の最大値(この問題の条件だと10000)に抑えられる(くらい重複している)。
という特徴を満たしていることになります。

この辺が感覚的につかめてくるともっと問題が解けるようになるのかもしれませんが、わからない場合はここに立ち返るようにしています。