A - Frog 1
問題：https://atcoder.jp/contests/dp/tasks/dp_a
解答：https://atcoder.jp/contests/dp/submissions/3938370
解法：dp[i]を「カエルが足場iに辿り着くまでに支払うコストの最小値」とする。dp[i] = min(dp[i-2] + abs(h[i-2] - h[i]), dp[i-1] + abs(h[i-1] - h[i]))であり、これを順番に求めてゆけばよい。
B - Frog 2
問題：https://atcoder.jp/contests/dp/tasks/dp_b
解答：https://atcoder.jp/contests/dp/submissions/3939065
解法：前問と同様に、dp[i]を「カエルが足場iに辿り着くまでに支払うコストの最小値」とする。dp[i] = min(dp[i-k] + abs(h[i-k] - h[i]), dp[i-k+1] + abs(h[i-k+1] - h[i]), ..., dp[i-1] + abs(h[i-1] - h[i]))である。min部分をループにして計算するとよい。
C - Vacation
問題：https://atcoder.jp/contests/dp/tasks/dp_c
解答：https://atcoder.jp/contests/dp/submissions/3939799
解法：dp[i][j]を「i日目に行動jを行った場合に、i日目までに得る幸福度の最大値」として計算してゆく。前日に同じ行動をとらないようにdp計算を行う。
D - Knapsack 1
問題：https://atcoder.jp/contests/dp/tasks/dp_d
解答：https://atcoder.jp/contests/dp/submissions/3940486
解法：dp[i][j]を「i番目までの商品を用いて重さがjとなるときの価値の最大値」として計算してゆく。
E - Knapsack 2
問題：https://atcoder.jp/contests/dp/tasks/dp_e
解答：https://atcoder.jp/contests/dp/submissions/3939799
解法：dp[i][j]を「i番目までの商品を用いて価値がjとなるときの重さの最小値」として計算してゆく。
F - LCS
問題：https://atcoder.jp/contests/dp/tasks/dp_f
解答：https://atcoder.jp/contests/dp/submissions/3952280
解法：dp[i][j]を「sをi文字目、tをj文字まで用いたときの共通文字列の長さの最大値」とする。sのi文字目とtのj文字目が同じとき、かつその時に限りchmax(dp[i][j], dp[i-1][j-1] + 1)の遷移をすればよい。復元は逆にdp[|s|][|t|]から"逆順に"dpを辿ってゆき、dp[i][j] = dp[i'][j'] + 1となるときに(i, j)のひとつ前として(i', j')を取得してゆく。
G - Longest Path
問題：https://atcoder.jp/contests/dp/tasks/dp_g
方針：dp[u]を「頂点uを始点するパス長の最大値」とすると、dp[u] = max{dp[v] + 1 | vはuの子頂点}となる。またuの出次数が0である場合、dp[u] = 0とする。遷移の方法のさせ方で複数解法がある。 また、連結成分が1つとは限らないところに注意が必要。
解答①：https://atcoder.jp/contests/dp/submissions/19009152
解法①：メモ化再帰。どの頂点から始めてもその頂点から出る辺を辿ってゆき、最終的に出次数0の頂点に辿り着き、その頂点からuまでの頂点のdp配列値が決まってゆく。いったん計算されてしまえばあとはそのdp配列値を使いまわすことができる。ちなみにメモ化再帰なので配列名はmemoにしています（趣味です）。
解答②：https://atcoder.jp/contests/dp/submissions/3959327
解法②：頂点番号が小さい頂点からトポロジカルソートを行う。トポロジカルソートの逆順に頂点を辿ると必ず出次数0の頂点からその頂点に入る頂点を辿ってゆくことができる。この順にdpを更新してゆくとよい。
H - Grid 1
問題：https://atcoder.jp/contests/dp/tasks/dp_h
解答：https://atcoder.jp/contests/dp/submissions/3943239
解法：dp[i][j]を「マス(i, j)までの経路の通り数」とする。マス(i, j)はマス(i-1, j)またはマス(i, j-1)から到達することができるので、その2マスからの遷移を考えればよい。
I - Coins
問題：https://atcoder.jp/contests/dp/tasks/dp_i
解答：https://atcoder.jp/contests/dp/submissions/3944117
解法：確率dp。dp[i][j]を「i番目までのコインを使い、表がj枚である確率」とする。dp[i][j]は「dp[i-1][j-1]から表がでる」「dp[i-1][j]から裏がでる」の2通りの出元がある。
J - Sushi
問題：https://atcoder.jp/contests/dp/tasks/dp_j
解答：https://atcoder.jp/contests/dp/submissions/3964795
解法：期待値dp。dp[{i, j, k}]を「寿司1個の皿がi枚、寿司2個の皿がj枚、寿司3個の皿がk枚のときに、全ての寿司がなくなるまでの操作回数の期待値」とする。状態の持たせ方の工夫として、寿司の個数さえわかれば皿の番号は不要である点、寿司0個の皿の枚数は自動的に分かる点に注意が必要である。
遷移が難しい。{i, j, k}の状況から次にどうなるかというと、下記の遷移がありえる。
- 確率i / nで{i-1, j, k}の状態になる
- 確率j / nで{i+1, j-1, k}の状態になる
- 確率k / nで{i, j+1, k-1}の状態になる
- 確率(n - i - j - k) / nで{i, j, k}の状態のまま
これらの状態は{i, j, k}から試行回数が1回多い状態であるため、期待値ベースで下記の式が成立する。（要証明）
dp[{i, j, k} ] = i / n * dp[{i-1, j, k}] + j / n * dp[{i+1, j, k}] + k / n * dp[{i, j+1, k-1}] + (n - i - j - k) / n * dp[{i, j, k}] + 1
両辺にdp[{i, j, k} ] があるため整理すると、numer = x + y + zとして
dp[{i, j, k} ] = i / numer * dp[{i-1, j, k}] + j / numer * dp[{i+1, j, k}] + k / numer * dp[{i, j+1, k-1}] + n / numer
が成り立つ。この式に従い、メモ化再帰すればよい。
K - Stones
問題：https://atcoder.jp/contests/dp/tasks/dp_k
解答：https://atcoder.jp/contests/dp/submissions/3969759
解法：ゲームdp。dp[i]を「残りの石の個数がi個のときに先手が勝てるか」を表すbool型の配列とする。このとき、dp[i]はdp[i-a[j]] (i - a[j] ≧ 0)に遷移することができるが、dp[i-a[j]]に一つでも先手負けのものがあればその手を用いて（先手になった）相手を負かせることが出来る。一方そのようなa[j]がなければ先手負けになる。よってiが小さい方からdp[i]を決めてゆけばよい。
L - Deque
問題：https://atcoder.jp/contests/dp/tasks/dp_l
解答：https://atcoder.jp/contests/dp/submissions/3969759
解法：dp[i][j]を「i+1からj番目までの数字でゲームをするときのX-Yの最大値」とする。ただし手番は1～nまでのカードを使用してその局面になった時の手番で考えるものとする。
(i, j)は(i-1, j)と(i, j+1)に遷移する。また手番ごとに最小値を取るか最大値を取るかが変わるため、それに注意して計算してゆく。
M - Candies
問題：https://atcoder.jp/contests/dp/tasks/dp_m
解答：https://atcoder.jp/contests/dp/submissions/19011906
解法：dp[i][j]を「i番目までの子供まで見たときに、残りの飴の数がj個のときの通り数」とする。N * K が大きいのでdp配列は前回のもののみを保持する(bef)。
i-1番目からi番目への遷移を考える。i番目の子供は0個以上a[i]個の飴を受け取ることができる。よってdp[j] = bef[j] + bef[j+1] + ...
+ bef[j+a[i]]である。また、dp[j-1] = bef[j-1] + bef[j] + ... + bef[j+a[i]-1]である。よって、両者の違いは+bef[j-1] - bef[j+a[i]]であり、jごとにこの差分を調整してdp[j]を計算してゆけばよい。
N - Slimes
問題：https://atcoder.jp/contests/dp/tasks/dp_n
解答：https://atcoder.jp/contests/dp/submissions/19024098
解法：dp[l][r]を「l番目からr番目のスライムを合体させるのにかかるコストの最小値」とすると、dp[l][r] = min{dp[l][l] + dp[l+1][r], dp[l][l+1] + dp[l+2][r], ..., dp[l][r-1] + dp[r][r]} + (a[l] + a[l+1] + ... + a[r])である。N≦400なので3乗が間に合うため、この計算を愚直にやるとよい。なお、メモ化再帰にすると計算順序を明示する必要がない。また、スライムが1体でいるときにコストはかかっていないため、dp[i][i] = 0であることに注意。
O - Matching
問題：https://atcoder.jp/contests/dp/tasks/dp_o
解答：https://atcoder.jp/contests/dp/submissions/19037739
解法：2^21 = 2097152なのでビットDPができる。dp[S]を「すでにペアが決まった女性の添字集合をSとしたときのペアの通り数」とする。このとき男性は先頭から決めてゆくすると男性の添字を記憶する必要がなくなる。貰うDPとすると計算量が測りやすい。配るDPは枝刈りにより計算量を落とせるらしい。公式解説で少し触れられている。
P - Independent Set
問題：https://atcoder.jp/contests/dp/tasks/dp_p
解答：https://atcoder.jp/contests/dp/submissions/19038900
解法：根付き木と考え、葉から順番に色を決めてゆくことを考える。ある頂点はその子の色に関わらず白色になる。また、その子が全て白の場合のみ黒色となる。よって、dp[i][j]を「頂点iの部分木の塗り方の総数。ただしj=0の時頂点iは白色、j=1のとき頂点iは黒色に塗られる。」とし、葉から値を決めてゆく。葉からの値の決め方はdfsの帰りがけに値を親に反映する。
別の視点としては、トポロジカルソートを行い、トポロジカルソートの逆順に頂点を見ていくと必ず子⇒親の順に頂点を見てゆくことが出来る。
トポロジカルソートを使った解法⇒https://atcoder.jp/contests/dp/submissions/19038640
Q - Flowers
問題：https://atcoder.jp/contests/dp/tasks/dp_q
解答：https://atcoder.jp/contests/dp/submissions/19039171
解法：dp[i]を「1番目からi番目までの花を使った時の美しさの最大値（i番目は必ず使う）」とする。このときdp[i] = max(dp[j] | j < i, h[j] < h[i]) + a[i]である。maxを取る際にi未満のjを走査しなければならず高速化が必要。ここでは1点更新最大値取得のセグメント木を用いる。
h[i]が1からnまでの順列となっているため、h[i]自体を添字に見立てるとよい。すなわちj番目の花の時には、セグメント木の前からh[j]番目にdp[j]を格納すれば、その後i > jなるiに対しては最初の項からh[i]番目未満までのdpの最大値を取得できる。
R - Walk
問題：https://atcoder.jp/contests/dp/tasks/dp_r
解答：https://atcoder.jp/contests/dp/submissions/19039600
解法：取得すべきパス長がかなり長く、愚直にはできそうにない。一旦次のようなdpを考える。dp[x][i][j]：「i番目の頂点からj番目の頂点に行くパス長xのパスの総数」とする。このとき遷移としては長さx-1のパス長に長さ1のパスをつなげればよいため、dp[x][i][j] = Σ dp[x-1][i][k] * a[k][j] である（k = 1～nの和）。この式をよく眺めると、実は行列の積の構造と同じである。初期状態は各頂点上からパスを考えることより、dp[0][i][j] = 1 (i = j)、dp[0][i][j] = 0 (i ≠ j)である。すなわちdp[0]は単位行列であり、dp[x] = A^xという行列累乗で求められることになる。
S - Digit Sum
問題：https://atcoder.jp/contests/dp/tasks/dp_s
解答：https://atcoder.jp/contests/dp/submissions/19040063
解法：桁DPを用いる。dp[i][j][e]を「先頭からi番目の数字までを使い、先頭からi番目までの数字の和がj (mod d)のである数の種類数。ただし、e = 1のときはもともと与えられたkと同じ数の種類数を表し、e = 0であればもともと与えられたkより小さい数の種類数を表す。」とする。（長いですね。。）
eの遷移が肝である。i-1桁目からi桁目への遷移について以下のことが言える。
- eが1から1に遷移する場合、i桁目の数字はsiである
- eが1から0に遷移する場合、i桁目の数字は0～s[i]-1である
- eが0から0に遷移する場合、i桁目の数字は0～9である
このようにeの場合分けにより遷移先の数字が決まり、それに伴い保持すべき数(mod d)も計算・更新できることとなる。
T - Permutation
問題：https://atcoder.jp/contests/dp/tasks/dp_t
解答：https://atcoder.jp/contests/dp/submissions/19041461
解法：すでに使用した番号の添字集合(bit)を持ちたくなるが、N≦3000なのでできない。i番目の数字のときに「その数字より大きい数がいくつ残っているか」を状態にするのが肝であり、遷移が少し複雑だがこれでうまくいく。
U - Grouping
問題：https://atcoder.jp/contests/dp/tasks/dp_u
解答：https://atcoder.jp/contests/dp/submissions/19042811
解法：dp[x]を「添字集合xに含まれるウサギについてのグループ分けによる得点の最大値」とする。dp[x]は以下のうちいずれかで最大値を取る。
- xに含まれる全てのウサギを同じグループにする
- y ⊂ x なる全てのyについて、xをyとx-yに分割してdp[y] + dp[x-y]に帰着させる（ただし、y ≠ ∅かつy ≠ x）
実装はメモ化再帰だとdp[y]とdp[x-y]が求めやすい。また、y ⊂ xなるyを走査する部分はy = (y-1) & xでyを更新してゆくと無駄なく計算できる。
