Educational DP Contest / DP まとめコンテスト

DPだとわかっていれば，意外とできるものです．
遷移方法を正しく書き下せるかがポイントです．

DPだけでなく，メモ化再帰も考えると理解が深まりそうです．

【2021.05.16~】

考え方

問題を解いていく中で，こう考えればよいのでは？と思ったことをまとめます．
なるべく機械的に考える方法を模索中です．

共通事項として，DPやメモ化再帰は，

• 最終ステップの答えが分かれば，その前のステップの答えがわかる
• 最初のステップの答えが分かれば，その次のステップの答えがわかる

という場合に有効です．

DP

• 前提
  
  • 小さな問題の解を使って，大きな問題を解くことができる．
  • ↑を漸化式として書き下すことができる．
• 注意
  
  • 漸化式を更新するのは，値が確定する1回だけにしたい．したがって，「どのようにループを回せば，更新するdpの値を確定できる情報が揃うか」を考える必要がある．また，それによって，初期化が必要な要素も変わる．
  • ↑で確定できる条件がわからず，漸化式の更新が1回で済まない場合，計算量が多くなる．この場合はメモ化再帰が有効．
• dpのつくりかた
  
  • 小さな問題の答えを使って，大きな問題の答えが計算できるようにつくる．

メモ化再帰

• 特徴
  
  • 値が確定する順序がわからなくても，とにかく必要になったら関数を呼び出せば良い．
  • 再帰関数は①dpが確定した時点で初めて計算する，②次からメモ（dp）を呼ぶ，ように定義できるのでDPだけを使う場合よりも計算量を抑えられる（DPは，値が確定しない場合も更新処理をする）．
• 注意
  
  • 逆に，再帰関数を呼び出してもdpが確定しない書き方はダメ．再帰関数を呼び出した時点で，dpが確定してしまい，その後更新できなくなる（メモしたdpが返される）ため．

A - Frog 1

シンプルです．遷移の仕方が2つあります．

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

# dp[i] = i からゴールまでのコストの最小値
INF = 10**9 + 1
dp = [INF]*N
dp[N-1] = 0

# dp[i] = min(dp[i+1] + abs(h[i+1]-h[i]), dp[i+2] + abs(h[i+2]-h[i]))
for i in reversed(range(N)):
  if i + 1 < N:
    dp[i] = min(dp[i], dp[i + 1] + abs(h[i + 1] - h[i]))
  if i + 2 < N:
    dp[i] = min(dp[i], dp[i + 2] + abs(h[i + 2] - h[i]))
    
print(dp[0])

B - Frog 2

遷移の仕方が増えました．
上のコードをじっと見れば，どうすればよいのかわかります．
いきなり，こちらを問われると難しいかも．．．

N, K = map(int, input().split())
h = list(map(int, input().split()))

# dp[i] = i からゴールまでのコストの最小値
INF = 10**9 + 1
dp = [INF]*N
dp[N-1] = 0

# dp[i] = min(dp[i+1] + abs(h[i+1]-h[i]), dp[i+2] + abs(h[i+2]-h[i]))
for i in reversed(range(N)):
  for j in range(1, K + 1):
    if i + j < N:
      dp[i] = min(dp[i], dp[i + j] + abs(h[i + j] - h[i]))
    
print(dp[0])

C - Vacation

添字が増えました．

N = int(input())
l = [list(map(int, input().split())) for _ in range(N)]

# dp[i-1][j] = i日目にjを選択したときのi~N日の幸福度の最大値
dp = [[0] * 3 for _ in range(N)]
dp[N - 1] = [l[N - 1][i] for i in range(3)]
for i in reversed(range(N - 1)):
  for j in range(3):
    for k in range(3):
      if k != j:
        dp[i][j] = max(dp[i][j], dp[i + 1][k] + l[i][j])

ans = max(dp[0])
print(ans)

D - Knapsack 1

入れない場合の遷移方法に気づかずに考え込んでしまい，蟻本の解法をカンニングしました．．．
Pythonで蟻本2-3 - 動的計画法（DP） - 競プロはじめました

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
  wt, vt = map(int, input().split())
  w.append(wt)
  v.append(vt)
  
# dp[i][j]=iコまで&重さj以下の最大価値
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
  for j in range(1, W + 1):
    # 入れる場合
    if j - w[i - 1] >= 0:
      dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
    # 入れない場合
    dp[i][j] = max(dp[i][j], dp[i - 1][j])
      
print(dp[N][W])

E - Knapsack 2

$W$でループさせることができないので，価値でループさせることを考えます（使える変数は，個数・価値・重さのみ）．

最後にdpから価値の情報を得るためには，dpの定義で「価値$j$以上」ではなく「価値$j$」としなくてはいけません．

dpのつくり方，初期化のしかた，$j$のループ範囲，最終的な出力方法など，つまづく要素がいくつもありました（これも，蟻本でやったはずなんですけどね．．．）．

N, W = map(int, input().split())
w, v = [], []
for _ in range(N):
  wt, vt = map(int, input().split())
  w.append(wt)
  v.append(vt)
  
# dp[i][j]=iコまで&価値jの最小重さ (解無しはINF)
INF = 10 ** 9 + 1
vmax = 10 ** 5
dp = [[INF] * (vmax + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
  for j in range(0, vmax + 1):
    # 入れる場合
    if j - v[i - 1] >= 0:
      dp[i][j] = min(dp[i][j], dp[i - 1][j - v[i - 1]] + w[i - 1])
    # 入れない場合
    dp[i][j] = min(dp[i][j], dp[i - 1][j])

for i, wmin in enumerate(dp[N]):
  if wmin <= W:
    ans = i
print(ans)

F - LCS

むずいです．部分列復元に関連する操作で，二重ループ内に$O(n)$の処理を入れるとTLEします．

【dpのつくりかた】
これまでのように，dp[i][j]は①$i,j$について単調に問題の大きさが変わり，②小さい問題から大きい問題への遷移を考える，ようにつくります．自然なのは
dp[i][j]=sのi文字目, tのj文字目までの最大部分列
とすることでしょう．

【遷移のつくりかた】
遷移の式がつくれない場合は，dpから見直すことになります．

dp[i][j]へ小さな問題から遷移するとき，「1)文字を加える」か「2)加えない」の2通りがあります．
1) 文字を加えてdp[i][j]へ遷移するとき，i) $s[i]$が加わる場合，ii) $t[j]$が加わる場合が考えられます．しかし，これらは$s[0]\sim s[i-1]$や$t[0]\sim t[j-1]$のどこまでが部分列に含まれているかを考慮しなければならず，遷移条件の判定が難しそうです．実は，iii) $s[i]$と$t[j]$の両方が加わる場合は，$s[i]=t[j]$かつdp[i-1][j-1] + s[i]と簡単に求められます．全ての遷移方法を考える必要があるFrogなどとは異なり，iii)だけで遷移が確定します．

しかし，ループの中で文字列の結合をするとTLEになるため，「dp[i][j]=sのi文字目, tのj文字目までの最大部分列の長さ」として，得られたdpから文字列を復元する必要があります．

2) 文字を加えずにdp[i][j]へ遷移するとき，dp[i][j]より小さい問題すべての中での最大部分列と同じ値となります．いま，dpの部分列長さが$i,j$のそれぞれについて単調増加（非減少）であるので，dp[i-1][j]とdp[i][j-1]だけを確認すれば十分です．

s = input()
t = input()

ls, lt = len(s), len(t)

# dp[i][j]=sのi文字目, tのj文字目までの最大部分列
dp = [[0]* (lt + 1) for _ in range(ls + 1)]
for i in range(1, ls + 1):
  for j in range(1, lt + 1):
    if s[i - 1] == t[j - 1]:
      # 文字が加わる場合:s[i],t[j]を含まないもののうち最大の部分列から遷移
      # ホントは dp[i][j] = dp[i - 1][j - 1] + s[i - 1] としたい
      dp[i][j] = dp[i - 1][j - 1] + 1
    else:
      # 文字が加わらない場合:dp[i][j]より小さい問題のうち最大の部分列と同じ
      # (※ dpはi,jのどちらに関しても単調増加)
      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

ans = []
i, j = ls, lt
while i >= 1 and j >= 1:
  if s[i - 1] == t[j - 1]:
    ans.append(s[i - 1])
    i -= 1
    j -= 1
  else:
    if dp[i][j] == dp[i - 1][j]:
      i -= 1
    else:
      j -= 1

print(''.join(reversed(ans)))

G - Longest Path

メモ化再帰

メモ化再帰なら，①更新順序がわからなくても候補を全て考えればOK，②同じテーブルを複数回呼び出しても問題ない，ためうまくいきます．

各頂点を1回ずつ，頂点とつながっている点を1回ずつ呼び出すので$O(N+M)$．

以下でfrmは不要ですが，from, toでセットにしていると意味がわかりやすいので入れておきました．

import sys
sys.setrecursionlimit(10 ** 6)

N, M = map(int, input().split())
frm = [[] for _ in range(N)]
t = [[] for _ in range(N)]
for _ in range(M):
  x, y = map(int, input().split())
  frm[y - 1].append(x - 1)
  t[x - 1].append(y - 1)
 
dp = [0] * N
def f(x):
  if dp[x] > 0:
    return dp[x]
  dp[x] = max([f(v) + 1 for v in t[x]] + [0])
  return dp[x]

print(max([f(x) for x in range(N)]))

DP失敗例（TLE）

こうするとTLE．

根本を見つけて，つながっている頂点を順に見ています．頂点 (i2 - 1) が1回で確定せず，何度も更新される可能性があります．つまり，確定した値だけを計算し，保存できません．

一方で，メモ化再帰では1回の処理で確定し，値を保存できています．

from collections import deque

N, M = map(int, input().split())
frm = [[] for _ in range(N)]
t = [[] for _ in range(N)]
for _ in range(M):
  x, y = map(int, input().split())
  frm[y - 1].append(x - 1)
  t[x - 1].append(y - 1)
  
# dp[i] = 頂点i+1までの最大パス長
dp = [0] * N

que = deque()
for i, vl in enumerate(frm):
  if not vl:
    que.append(i)

while len(que):
  i = que.popleft()
  for i2 in t[i]:
    dp[i2] = dp[i] + 1
    que.append(i2)
  
print(max(dp))

H - Grid 1

DP

前問までに比べると簡単です．

1. 一番下の行を右から左に行を見ていく
2. 見終わったら上の行の右端で同じことをする

として，「今見ているマスから$(H,W)$へ行くまでの経路数」をdpで記録していきます．

見ているマスから移動できる，①自分の下のマス，②自分の右のマス，は前ステップまでですでに求めています．よって，dp[自分のマス] = dp[下のマス] + dp[右のマス]で更新できます．

あとは，初期条件，壁，端などの例外処理をifで分岐させるだけです

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

mod = 10 ** 9 + 7

# dp[i][j] = (i+1,j+1)から(H,W)までの経路数
dp = [[0] * W for _ in range(H)]
dp[H - 1][W - 1] = 1

for i in reversed(range(H)):
  for j in reversed(range(W)):
    if i == H - 1 and j == W - 1:
      dp[i][j] = 1
    if A[i][j] == '#':
      dp[i][j] = 0
    else:
      if i + 1 <= H - 1:
        dp[i][j] += dp[i + 1][j]
      if j + 1 <= W - 1:
        dp[i][j] += dp[i][j + 1]
      
print(dp[0][0] % mod)

メモ化再帰

メモ化再帰では，dpを一回で確定できるような書き方にする必要があります．

また，再帰関数中でdpが呼び出される前に「添字が範囲外なら0を返す」処理を入れることで，仮想的にdpの添字範囲を広げることができます（全てメモする必要はなく，関数の定義域がメモ(dp)の添字範囲を超えても良い！）．

import sys
sys.setrecursionlimit(2000)

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

mod = 10 ** 9 + 7

# dp[i][j] = (i+1,j+1)から(H,W)までの経路数
dp = [[-1] * W for _ in range(H)]
def f(i, j):
  if i >= H or j >= W:
    return 0
  if dp[i][j] >= 0:
    return dp[i][j]
  if i == H - 1 and j == W - 1:
    dp[i][j] = 1
  elif A[i][j] == '#':
    dp[i][j] = 0
  else:
    dp[i][j] = f(i + 1, j) + f(i, j + 1)
  return dp[i][j]
      
print(f(0, 0) % mod)

I - Coins

これも，割と素直な問題です．

DP

N = int(input())
p = list(map(float, input().split()))

# dp[i][j] = i枚目までで表がj回出る確率
dp = [[''] * (N + 1) for _ in range(N + 1) ]
dp[0] = [0 if i else 1 for i in range(N + 1)]

for i in range(1, N + 1):
  for j in range(N + 1):
    if i < j:
      dp[i][j] = 0
    elif j == 0:
      dp[i][0] = dp[i - 1][0] * (1 - p[i - 1])
    else:
      dp[i][j] = dp[i - 1][j - 1] * p[i - 1] + dp[i - 1][j] * (1 - p[i - 1])
      
print(sum(dp[N][j] for j in range(N//2 + 1, N + 1)))

メモ化再帰

import sys
sys.setrecursionlimit(3000**2)

N = int(input())
p = list(map(float, input().split()))

# dp[i][j] = i枚目までで表がj回出る確率
dp = [[-1] * (N + 1) for _ in range(N + 1) ]

def f(i, j):
  if dp[i][j] >= 0:
    return dp[i][j]
  if i == 0 and j == 0:
    dp[i][j] = 1
  elif i < j:
    dp[i][j] = 0
  elif j == 0:
    dp[i][j] = f(i-1, j) * (1 - p[i - 1])
  else:
    dp[i][j] = f(i - 1, j - 1) * p[i - 1] + f(i - 1, j) * (1 - p[i - 1])
  return dp[i][j]
      
print(sum(f(N, j) for j in range(N//2 + 1, N + 1)))

J - Sushi

状態$\{a_{n}\}_{n}$からの操作回数を与える確率変数$X_{\{a_{n}\}_{n}}$の期待値$E[X_{\{a_{n}\}_{n}}]$を求める問題です．

この期待値は，皿の並び順にはよりません．つまり，1個，2個，3個の寿司の個数$(i,j,k)$だけで決まってしまいます．

条件付き期待値の関係式（参考：条件付き期待値の計算例 - Notes_JP）から

\begin{aligned}
&E[X] \\
&=(1 + E[X]) \cdot p(0\text{個の皿を当てる}) \\
&\quad + E[X|i\to (i-1)] \cdot p\bigl(1\text{個の皿を当てる}\bigr) \\
&\quad + E[X|(i,j)\to (i+1, j-1)] \cdot p\bigl(2\text{個の皿を当てる} \bigr) \\
&\quad + E[X|(j,k)\to (j+1, k-1)] \cdot p\bigl(3\text{個の皿を当てる}\bigr) \\
\end{aligned}

となります．

上式を$E[X]$について解き，1個，2個，3個の寿司の個数$(i,j,k)$のときの期待値を$\mathrm{dp}[i][j][k]$と表せば，

\begin{aligned}
&\mathrm{dp}[i][j][k] \\
&=\bigl(1 + \mathrm{dp}[i][j][k] \bigr) \cdot p(0\text{個の皿を当てる}) \\
&\quad
+ \bigl(1 + \mathrm{dp}[i-1][j][k] \bigr) \cdot p\bigl(1\text{個の皿を当てる}\bigr) \\
&\quad
+ \bigl(1 + \mathrm{dp}[i+1][j-1][k] \bigr) \cdot p\bigl(2\text{個の皿を当てる} \bigr) \\
&\quad
+ \bigl(1 + \mathrm{dp}[i][j+1][k-1] \bigr) \cdot p\bigl(3\text{個の皿を当てる}\bigr)
\end{aligned}

なので

\begin{aligned}
&\biggl[1 - p(0\text{個の皿を当てる}) \biggr]\mathrm{dp}[i][j][k] \\
&= 1 \\
&\quad + \mathrm{dp}[i-1][j][k] \cdot p\bigl(1\text{個の皿を当てる}\bigr) \\
&\quad + \mathrm{dp}[i+1][j-1][k] \cdot p\bigl(2\text{個の皿を当てる} \bigr) \\
&\quad + \mathrm{dp}[i][j+1][k-1] \cdot p\bigl(3\text{個の皿を当てる}\bigr)
\end{aligned}

となります．よって，

\begin{aligned}
&\mathrm{dp}[i][j][k] \\
&=\frac{N}{i+j+k}\biggl[ 1 \\
&\qquad\qquad\qquad
+ \mathrm{dp}[i-1][j][k] \cdot \frac{i}{N} \\
&\qquad\qquad\qquad
+ \mathrm{dp}[i+1][j-1][k] \cdot \frac{j}{N} \\
&\qquad\qquad\qquad
+ \mathrm{dp}[i][j+1][k-1] \cdot \frac{k}{N} \biggr]
\end{aligned}

なので，左辺のdpは右辺の辞書順で小さい$(i,j,k)$のdpに帰着しました．

DP

$O(N^{3})$なので特に工夫しなくても間に合うと思いきや，よけいなループをしないように，範囲や分岐で処理しないとTLEしてしまいました（なんでだろう？）．

また，dpの初期化を-1ではなく''としてもTLEでした（これも，理由がわからない）．

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

num1, num2, num3 = a.count(1), a.count(2), a.count(3)

# dp[i][j][k] = (残り1, 残り2, 残り3) = (i,j,k)のときの期待値
dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0

for k in range(num3 + 1):
  for j in range(num2 + num3 - k + 1):
    for i in range(num1 + num2 + num3 - j - k + 1):
      if i == j == k == 0:
        continue
      tmp = N 
      if 0 < i:
        tmp += i * dp[i - 1][j][k]
      if 0 < j:
        tmp += j * dp[i + 1][j - 1][k]
      if 0 < k:
        tmp += k * dp[i][j + 1][k - 1]
      dp[i][j][k] = tmp / (i + j + k)

print(dp[num1][num2][num3])

メモ化再帰

なんとかTLEしなかったコードです．他に高速化の余地があるのかわからない．．．

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

# dp[i][j][k] = (残り1, 残り2, 残り3) = (i,j,k)のときの期待値
dp = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0

def f(i, j, k):
  if dp[i][j][k] >= 0:
    return dp[i][j][k]
  res = N / (i + j + k)
  if 0 <= i - 1:
    res += f(i - 1, j, k) * i / (i + j + k)
  if 0 <= j - 1:
    res += f(i + 1, j - 1, k) * j / (i + j + k)
  if 0 <= k - 1:
    res += f(i, j + 1, k - 1) * k / (i + j + k)
  dp[i][j][k] = res
  return res

num1 = sum(1 if ai == 1 else 0 for ai in a)
num2 = sum(1 if ai == 2 else 0 for ai in a)
num3 = sum(1 if ai == 3 else 0 for ai in a)
print(f(num1, num2, num3))

【余談】
最初，リストの初期化を[[[-1] * (N + 1)] * (N + 1)] * (N + 1)としてバグりました．詳しくは以下「2次元配列（リストのリスト）を初期化する際の注意」を参照：
Pythonのリスト（配列）を任意の値・要素数で初期化 | note.nkmk.me

K - Stones

DP

N, K = map(int, input().split())
a = list(map(int, input().split()))

# dp[i] = 残りi個で手番の人が勝つ確率
dp = [0] * (K + 1)
dp[0] = 0

for i in range(1, K + 1):
 for ai in a:
  if i - ai >= 0 and dp[i - ai] == 0:
    dp[i] = 1

print('First' if dp[K] == 1 else 'Second')

L - Deque

【類題】
D - Game in Momotetsu World

DP

これもdpの初期化を''とすると，めちゃ遅くなります．この初期化は，バグ取りをするときだけにしたほうが良さそうです．

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

# dp[i][j] = (ai,...,aj)から始めたときの自分-相手の最大値
dp = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
  dp[i][i] = a[i - 1]

for j in range(1, N):
  for i in range(1, N):
    if i + j <= N:
      dp[i][i + j] = max(- dp[i + 1][i + j] + a[i - 1], - dp[i][i + j - 1] + a[i + j - 1])

print(dp[1][N])

メモ化再帰

間に合うコードを書くのは難しいです．読み込み方法から工夫する必要があります．

例：
Submission #22654217 - Educational DP Contest

M - Candies

DP

$i$番目までに$j$個配る方法 ($\mathrm{dp}[i][j]$) は，$i$番目に$k$個配ると考えれば，ざっくり

\begin{aligned}
&\mathrm{dp}[i][j] \\
&=\sum_{k} dp[i-1][j-k]
\end{aligned}

です．

制約までちゃんと考えると，和を2つ目の添字の降順に考えれば

\begin{aligned}
&\mathrm{dp}[i][j] \\
&=\sum_{k=0}^{\min(j,a_{i})} dp[i-1][j-k]
\end{aligned}

と表すことができ，和を2つ目の添字の昇順に考えれば

\begin{aligned}
&\mathrm{dp}[i][j] \\
&=\sum_{k= \max(0,j-a_{i})}^{j} dp[i-1][k]
\end{aligned}

となります．この式は「累積和」の形になっており，2つ目の添字のループの外に出すことができます．

【参考】
Pythonで累積和・累積積（itertools.accumulate） | note.nkmk.me

import itertools

N, K = map(int, input().split())
a = list(map(int, input().split()))
M = 10**9 + 7

# dp[i][j] = i番目までにj個配る場合の数
dp = [[0] * (K + 1) for _ in range(N + 1)]
dp[0] = [0 if i else 1 for i in range(K + 1)]

for i in range(1, N + 1):
  tmp = list(itertools.accumulate(dp[i - 1]))
  for j in range(K + 1):
    if j - a[i - 1] > 0:
      dp[i][j] = (tmp[j] - tmp[j - a[i - 1] - 1]) % M
    else:
      dp[i][j] = tmp[j] % M
    
print(dp[N][K])

DP (蟻本)

蟻本の「重複組合せ」と同じ問題です．
Pythonで蟻本2-3 - 動的計画法（DP） - 競プロはじめました

$i$番目までに$j$個配る方法 ($\mathrm{dp}[i][j]$) は，

1. $i-1$番目までに$j$個配る方法 ($\mathrm{dp}[i-1][j]$)
2. $i$番目の1個を確保した上で$i$番目までに$j-1$個配る方法 ($\mathrm{dp}[i][j-1]$)

の和になります．ただし，個数制限があるので，2つめの場合の数で$a_{i}$個を超えた分を除く必要があります．$\mathrm{dp}[i][j-1]$は$i$番目が$a_{i}$個以下となるように求めています．一方で，いま$i$番目の1個を確保しているので，$\mathrm{dp}[i][j-1]$で$i$番目が$a_{i}$個となる場合は除く必要があります．これは，$i$番目の$a_{i}$個を確保して考えれば，$\mathrm{dp}[i - 1][j - (a_{i}+1)]$となります．

以上より，

\begin{aligned}
& \mathrm{dp}[i][j] \\
&=\mathrm{dp}[i-1][j] \\
&\quad
+ \mathrm{dp}[i][j-1] \\
&\quad
- \mathrm{dp}[i - 1][j - (a_{i}+1)]
\end{aligned}

となります（*1）．

N, K = map(int, input().split())
a = list(map(int, input().split()))
M = 10**9 + 7

# dp[i][j] = i番目までにj個配る場合の数
dp = [[0] * (K + 1) for _ in range(N + 1)]
dp[0] = [0 if i else 1 for i in range(K + 1)]

for i in range(1, N + 1):
  for j in range(K + 1):
    res = dp[i - 1][j]
    if j > 0:
      res += dp[i][j - 1]
    if j > a[i - 1]:
      res -= dp[i - 1][j - a[i - 1] - 1]
    dp[i][j] = res % M
    
print(dp[N][K])

N - Slimes

DP

import itertools

N, *a = map(int, open(0).read().split())
acc = list(itertools.accumulate(a))

# dp[i][j]=[i,j]の分解に要する最小コスト
INF = 2 ** 60
dp = [[INF] * (N + 1) for _ in range(N + 1)]
for i in range(N + 1):
  dp[i][i] = 0

for j in range(1, N):
  for i in range(1, N - j + 1):
    res = INF
    for k in range(i, i + j):
      res = min(res, dp[i][k] + dp[k + 1][i + j])
    res += acc[i + j - 1]
    if i > 1:
      res -= acc[i - 2]
    dp[i][i + j] = res

print(dp[1][N])

次の書き方が，シンプルでいいな，と思いました．累積和の先頭にゼロがあると便利，ということですね．
Submission #3949878 - Educational DP Contest

メモ化再帰

コストの取り得る最大値は$N=400$のとき

\begin{aligned}
&10^{9} [2(N-1) + (N-2)+(N-3) +\cdots + 1] \\
&=10^{9}[2(N-1) + (N-1)(N-2)/2] \\
&=10^{9} \frac{1}{2} (N-1)(N+2) \\
&=8.0199 \times 10^{13}
\end{aligned}

です．これに注意してINFを設定します．

import itertools
import sys
sys.setrecursionlimit(160000)

N, *a = map(int, open(0).read().split())
acc = list(itertools.accumulate(a))

# dp[i][j]=[i,j]の分解に要する最小コスト
INF = 2 ** 60
dp = [[INF] * (N + 1) for _ in range(N + 1)]

def f(i, j):
  if i == j:
    return 0
  if dp[i][j] < INF:
    return dp[i][j]
  res = INF
  for k in range(i, j):
    res = min(res, f(i, k) + f(k + 1, j))
  res += acc[j - 1]
  if i > 1:
    res -= acc[i - 2]
  dp[i][j] = res
  return res

print(f(1, N))

O - Matching

DP - 1

N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]

M = 10 ** 9 + 7

# dp[S] = 集合Sの女性と1~|S|の男性をペアにする場合の数
dp = [0] * (1 << N)
dp[0] = 1

for S in range(1, 1 << N):
  i = bin(S).count('1')
  for j in range(N):
    if S & (1 << j) and a[i - 1][j]:
      dp[S] = (dp[S] + dp[S & ~(1 << j)]) % M
      
print(dp[(1 << N) - 1])      

P - Independent Set

再帰（実質DP）

木DPと呼ぶそうです．

ある頂点から子ノードをたどっていく回し方はforで上手く表現できないので，代わりに再帰を使います．forのかわりにつかっており，1回しか呼ばれないのでメモ化はしません．

実行速度はPythonの方がPyPyよりもはるかに速かったです．

import sys
sys.setrecursionlimit(10 ** 5)

M = 10 ** 9 + 7

N = int(input())
g = [[] for _ in range(N)]
for _ in range(N - 1):
  x, y = map(int, input().split())
  g[x - 1].append(y - 1)
  g[y - 1].append(x - 1)

# dp[i][0/1] = 頂点iが0/1のとき， 根iの部分木を塗る場合の数(0:白, 1:黒)
dp = [[-1] * 2 for _ in range(N)]

# for のかわりに再帰関数で子ノードをたどるように回す 
def f(cur, par):
  res0, res1 = 1, 1
  for chi in g[cur]:
    if chi != par:
      f(chi, cur)
      res0 *= dp[chi][0] + dp[chi][1]
      res1 *= dp[chi][0]
      res0 %= M
      res1 %= M
  dp[cur][0], dp[cur][1] = res0, res1

f(0, -1)
print((dp[0][0] + dp[0][1]) % M)

Q - Flowers

DP

慣れない発想が必要で難しいです．

セグメント木はこちら（Segment Tree のお勉強(1) | maspyのHP）を使いました．

# https://judge.yosupo.jp/submission/7795
class SegTree:
    X_unit = 0
    X_f = max

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = x
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def set_val(self, i, x):
        i += self.N
        self.X[i] = x
        while i > 1:
            i >>= 1
            self.X[i] = self.X_f(self.X[i << 1], self.X[i << 1 | 1])

    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = self.X_f(vL, self.X[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.X_f(self.X[R], vR)
            L >>= 1
            R >>= 1
        return self.X_f(vL, vR)

# ---
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

M = 2 * (10 ** 5) + 1
seg = SegTree(M)
seg.build([0] * M)

for i in range(N):
  seg.set_val(h[i], seg.fold(0, h[i]) + a[i])
  
print(seg.fold(0, M))

R - Walk

DP

S - Digit Sum

DP

T - Permutation

DP

U - Grouping

DP

V - Subtree

DP

W - Intervals

DP

X - Tower

DP

Y - Grid 2

DP

Z - Frog 3

DP

*1:上で導いた式から

\begin{aligned} &\mathrm{dp}[i][j] \\ &=\sum_{k=0}^{\min(j,a_{i})} \mathrm{dp}[i-1][j-k] \\ &=\sum_{k=1}^{\min(j,a_{i})} \mathrm{dp}[i-1][j-k] + \mathrm{dp}[i - 1][j] \\ &=\sum_{k=0}^{\min(j,a_{i}) - 1 } \mathrm{dp}[i-1][j-1-k] + \mathrm{dp}[i - 1][j] \end{aligned}

なので，①$j \leq a_{i}$なら

\begin{aligned} &\mathrm{dp}[i][j] =\sum_{k=0}^{j} \mathrm{dp}[i-1][j-k] \\ &= \sum_{k=0}^{j - 1 } \mathrm{dp}[i-1][j-1-k] + \mathrm{dp}[i - 1][j] \\ &=\mathrm{dp}[i][j-1] + \mathrm{dp}[i - 1][j] \end{aligned}

，②$j > a_{i}$なら（$j - 1 \geq a_{i}$なので）

\begin{aligned} &\mathrm{dp}[i][j] =\sum_{k=0}^{a_{i}} \mathrm{dp}[i-1][j-k] \\ &=\sum_{k=0}^{a_{i} - 1 } \mathrm{dp}[i-1][j-1-k] + \mathrm{dp}[i - 1][j] \\ &=\sum_{k=0}^{a_{i}} \mathrm{dp}[i-1][j-1-k] + \mathrm{dp}[i - 1][j] \\ & \quad - \mathrm{dp}[i-1][j-1-a_{i}] \\ &=\mathrm{dp}[i][j-1] + \mathrm{dp}[i - 1][j]- \mathrm{dp}[i-1][j-1-a_{i}] \end{aligned}

と示すこともできます．