はじめに

はじめまして，競プロを勉強している緑コーダー(初心者)ばしん(Basin)といいます。
緑色になるまで，いろいろなアルゴリズムを学んでいましたが，そのうちに動的計画法(DP)というアルゴリズムが大好きです。
しかし，周りの人にDPをいうと，「なかなか難しいアルゴリズムだな~」というイメージがよく付けられてしまい，今の私でも，完全にDPを理解しているや，DPに関する問題絶対解ける，などの自信がないです。
なので，本記事の目的は，DPをアルゴリズムよりも，一つの考え方として，私の経験や理解しているDPの進み方(問題の解き方)についてお話ししたいと思います。
また，本記事では，読者がDPを全く知らない，もしくは少し知っていてもコンテスト中にピンとこない，もしくは書きにくいことと想定し，DPが上達，または特定なDPの遷移について学びたい読者に対しては本記事が向いていないと考えています。

DPとは

厳密にいうと動的計画法(Dynamic Programming)と呼ばれますが，ざっくり言うと一つの問題をいくつかの部分問題に分かれて，それぞれの部分問題の結果から，最終の結果に影響を及す手法です。
世の中には，DPをアルゴリズムの1種だと認識していますが，私的にはDPを一つの考え方として考えたりもします。

競プロでのDP(AtCoder ABCを代表的に)

AtCoderのABCコンテストは，D以降の問題であれば，基本的どこにDPが出れてもおかしくありません。また，難易度としても問題番後のように幅広く存在します。そして，EDPCやTDPCというようなDPだけの(練習?)コンテストも存在します。
また，DPという幅広い概念から，さらに典型ごとに分類することも珍しくありません。例えば，以下の典型的なDPが存在します。

ナップサックDP
部分和DP
LCS
確率DP
桁DP
などなど

ここで，なぜこういう典型の分類があるのか？ということを考えていました。他のアルゴリズムと比べて，例えば幅優先探索や深さ優先探索，二分探索などのアルゴリズムでは，「これらの典型パターンや典型問題があるよー」ということと，「それぞれのパターンがこういうところが違うよー」，「こう考えばDFSだよ」などのようなことはあまり聞いたことありません。その理由は，DPという広い概念から，具体的にやり方が違うところから分類され，さらにそれぞれの典型問題や，やりかたから名前を付けられただろうと考えていました。

DPを解くための流れ

ここでは，簡単にDP問題の解き方について紹介します。主には以下の5点を順番に考えれると，この問題はDPで解けると思っています。(貪欲法とDPを混ぜて解釈する記事もありますが，本記事では最適解を求められるかどうかで区別します。)

この問題は，DPで解けるのか(貪欲ではないのか)
$dp[i]$，または$dp[i][j]$などでは何を表すのか
最初は，DPテーブルをどうすればよいのか(初期化)
どういう遷移になるのか
結果的に何を出力すればいいのか

1. この問題は，DPで解けるのか(貪欲ではないのか)

これは最初のステップですが，最も難しいステップだと考えています。そして，一番DPと混乱しそうなのは貪欲法です。
貪欲法では，途中にある部分問題の結果にかかわらず，常に最適な選択があります。つまり，貪欲法が適用される問題では，入力とは関係せず最適な流れがきっとあります(例えば，複数の選択肢があるときには常に順番で選択するなど)。
貪欲法では，決まった順番で問題を解けることは証明できます。そして貪欲法っぽいけど貪欲法ではないと判断された場合，基本的にDPを考えるべきだと思います。

2. dp[i]，またはdp[i][j]などでは何を表すのか

ここから，DPについての考え方に入ります。
まず，この問題ではDPを使って何を表したいのかを考えなければいけません。具体的には，「DPを使うと，何次元DPを使えば足りるか？」と「それぞれの次元でどの変数の変化を入れるか」を考えばいいです。
ここでは次元を決まった後に，例えば「$dp[i]$とは？」，または「$dp[i][j]$をは？」という質問から，一文程度でまとめてくれれば，成功です。

3. 最初は，DPテーブルをどうすればよいのか(初期化)

ここでは，DPの遷移をうまく行くための準備を行います。
最初の入力がないと，次からの遷移ができなくなります。なので，全体の遷移を行う前に，どこかで，なにかの初期化をべきかの考えは必要がありつつ，全体的にどういう値として初期化すればいいかも考えるべきです。
まず，全体的な初期化に対して，主には求めたいものによります。例えば，最小値であれば，全体的に大きい数値を初期化して，さらに遷移するときに$min$関数などを使って更新するイメージです。また，可能かどうかを求める問題では，最初に全体を$False$した後に，条件や遷移によって一部ずつ$True$になる更新もあります。
次には，初期状態についてです。最初の状況について考えるので，主なところは，$dp[0]$, $dp[0][0]$, $dp[0][i]$, $dp[i][0]$あたりはよく設定します(ここの$i$というのは，その行または列全体のことを指しています)。もちろん木構造や，区間DPなどの場合では他のところに初期化する場合もあります。
それぞれ何を設定するかにはケースバイケースですが，例えば，$dp[i] := $数字$i$になるための必要最小の操作数とし，またその数字が$0$から変化し始まることがわかれば，最初的には$dp[0] = 0$と設定すればふさわしいと考えられます。

4. どういう遷移になるのか

ここでは，DPの醍醐味である遷移の話に入ります。
DPの遷移では，私個人的には漸化式のような感じだと理解しています。
しかし，漸化式だけと言っても$i$番目から$i + 1$番目など後ろに遷移する，もしくは$i$番目から$i - 1$番目など前に遷移するケースがあります(いわゆる配るDP，貰うDPとも呼ばれます)。もちろん木構造などのよって他の遷移の方法もあります。この辺の基本的な考え方としては，後ろの要素が前のいくつかの要素でまとめる感じなのか，もしくは前の要素が後ろの要素に発散する感じかの考えやすいほうで進めばよいです。
方向性を解決したあと，次には式を書くことを解決します。前にも話したように，DPの式は基本的に漸化式のように見えます。つまり，DP全体を使って値の最大化をしたい場合，かつ前に遷移することが決めた場合，よく$dp[i][j] = max(dp[i][j], dp[i - 1][*]+ *)$のように書きます。すなわち，$i$行目の$j$列目要素は$i - 1$行目のどの列の値，プラスどういう定数によって決める可能性があるか(元の$dp[i][j]$の値を超える可能性があるか)を考える必要があります。

5. 結果的に何を出力すればいいのか

ここまで，我々はもうすでにDPの初期化から遷移まできちんと決めました。残りとしては，求められたいものを出力するだけです。
基本的に，テーブルの右下($N$行$M$列のテーブルであれば$dp[N - 1][M - 1]$)の要素を出力すればよいですが，場合によって他の要素を考えることもあります。しかし，よく考えるべきところは，最後の行や最後の列から注目することです。

具体例から流れを示す

先ほどはテキストでDPの流れを紹介しましたが，文字だけで曖昧ですし理解することも難しいと思いますので，次からには1つの具体例(ABC204-D Cooking)から紹介します。

まず，この問題はDPで解ける問題なのかを考えます。時間が少ない方から順番に選んで，全体の時間の半分近くにたどり着いたらその時間が求めた最小値であるっていう貪欲法を考えられるかもしれませんが，実は$T = \lbrace1, 2, 4, 3 \rbrace$のようになる場合最小である$5$にならず，実装によって$\lbrace3, 7 \rbrace$や$\lbrace4, 6 \rbrace$という組み合わせとなり，全体的な必要時間は明らかに$5$を超えていることがわかります。
貪欲法が解けず，(ビット)全探索にも明らかに計算量が膨大であるので，そもそもDPの考えに入りますが，集合から一部の要素を抽出してその和についての操作することから，DPの典型である「部分和問題」として考えます。（次からには部分和の実装について書きますが，すでにご存知する方には適宜飛ばしても大丈夫です。）

次には，$dp[i][j]$にはどういうことを記述するかを決めます。一次元配列を回しながら決めるDPであれば，$dp[i]$の意味は$i$番目の要素まで求められた最大最小値(int型)や可能不可能(bool型)にする方が多いです。二次元の場合，$dp[i][j]$とは$i$番目の要素まで求めた値が$j$になる可能性があるか，または$j$にするためのコストの最大最小値を表すことが一般的に考えます。
よって今回の問題はまず$i$の方は配列が回したところを記述することにします。また，列の方にはいくつかの要素を選らんだ総和が$j$にします。つまり，全体的には$dp[i][j] := T[i]$まで適当にいくつかの要素を選んで，その総和を$j$になることができるかとします。
以上からまとめると，$dp[i][j] := i$番目までの要素からいくつかを選び，その総和が$j$になれるか($True$)否か($False$)に基づいてテーブルを作ります。ここで，DPテーブルは$1$行目から$N$行行目，$1$列目から$sum(T)$列目まで作ればいいですが，何もしないことを書きやすいため，それぞれ$0$行目と$0$行目を追加した方が楽かもしれません。

テーブル全体を決めたので，次には初期化に進みます。最初にある全体の初期化では，常に「何も操作しない場合になる結果」にする方がよいです。例えばこの問題に対して，集合から何も選ばないと，任意の$j$になるかを考えると，明らかにNoとなるので全体的には$False$にします。
そして，特別な初期化として，配列$T$を探索する前に，選んだ要素が$0$にしかならないことがわかります。よって，$dp[0][0] = True$だけ変更します。
以上によって，このようなプログラムを最初に書けます。

dp = [[False] * (sum(T) + 1) for i in range(N + 1)]
dp[0][0] = True

ここまで，$0$行目には決まりました。次には$1$行目から$N$行目までを遷移で決めます。
この問題では，各要素$T[i]$に対して，それを選ぶ/選ばないの2通りしかないので，それぞれに基づく遷移を書けばよいです。

$T[i]$を選ぶ場合，$i$行目で組めるすべての数字に対して，その数字を$i + 1$行目で$T[i]$を足した値になることが可能です。
$T[i]$を選ばない場合，$i$行目で組めるすべての数字に対して，$i + 1$行目で$T[i]$を足さないのでその値のままになることも可能です。
まとめると，$dp[i][j]$が$True$の場合，$dp[i + 1][j + T[i]]$と$dp[i + 1][j]$両方が$True$になれます。
ここの$i - 1$を$i$に関するfor文でまとめて書くと，以下のプログラムで遷移を書けます。

for i in range(N):
  for j in range(sum(T) + 1):
      if dp[i][j]:
      dp[i + 1][j + T[i]] = True #選ぶ場合
        dp[i + 1][j] = True #選ばない場合

ここまで，DPテーブルを完成しました。最後に，何を出力すればよいかを考えればよいです。
ここで問題文に戻ります，この問題は，すべての料理を作るための最短時間を求めているが，我々のDPでは一部の料理を規定時間$j$でちょうど作れるかを求め，そしてこの時間では1個のオーブンだけを使うことを前提として求めました(言い換えると，二つのオーブンを同時に起動する遷移は書いていませんでして，そもそも書くのもより難しくなります)。ここで，もう片方のオーブンの利用時間は残った料理を作る時間となり，全体的な最短時間ではこの二つのオーブンの利用時間のうちの最大値であることがわかります。なので，それぞれの部分和に対して，最短時間の最小値を全探索すればよいです。
つまり，配列$T$を回し終わった時点で，料理をいくつか選んで$j$分ちょうど使うことが可能なすべての$j$に対して，$j$と$sum(T) - j$のうちの最大値が全体の最小時間となる可能性があります。
従って，最後の出力部は以下のように書けます。

ans = sum(T) #最小時間の初期化:可能な範囲での最大値を使って初期化する
for i in range(sum(T) + 1):
  #N種類の料理からいくつか選んで，ちょうどi分で作り終わらせることができる場合
  if dp[-1][i]: 
    #i:選んだ料理を作るオーブンの利用時間
    #sum(T) - i:選んでいない料理を作るオーブンの利用時間
    ans = min(ans, max(i, sum(T) - i)

print(ans)

これでこの問題は全体的におしまいします。コードの全体は以下のようになります。

N = int(input())
T = list(map(int, input().split()))

dp = [[False] * (sum(T) + 1) for i in range(N + 1)]
dp[0][0] = True

for i in range(N):
  for j in range(sum(T) + 1):
    if dp[i][j]:
      dp[i + 1][j] = True
      dp[i + 1][j + T[i]] = True

ans = sum(T)
for i in range(sum(T) + 1):
  if dp[-1][i]:
    ans = min(ans, max(i, sum(T) - i))

print(ans)

おわりに

ここで，DPの紹介については終わります。
今回は，DPの範囲でもかなり典型である部分和問題を少し変形した問題を扱いました。具体的になぜDPを使うのか，DPテーブルの定義，初期化，遷移の書き方と出力についての考察法をそれぞれ個人の経験に基づいて書きました。
私は競プロを始まった以来，DPはとても好きて，アルゴリズムよりも考え方として認識し，「こういうことを考えるものはDPであろう」と考えています。しかし，最初にお話ししたように，DPと言ってもその範囲が結構幅広く，私がいまだに理解していないDPもたくさん存在するだろうと思っています。よって，特に水色以上のdiffを持っているDP問題に対して，このような考え方が通さない場合があっても問題が悪いわけでなく，この記事の筆者である私が悪いであることをご認識いただければ幸いです。

私とDP