一次元ナップサック DP (部分和問題)
ナップサック問題 (重さの総和(w)を超えない価値の最大値)
dp[i番目][重さ] = 価値の最大値
部分和数え上げ問題 (総和(n) : 何通りか)
dp[i番目][n] = 何通り
最小個数部分和問題 (総和(n) : 最小個数)
dp[i番目][数] = 最小個数
一次元ナップサック DP (区間分割)
発電計画問題 (区間分割 : 得られる利得の最大値)
dp[i秒] = 利得の最大値
二次元ナップサック DP (比較)
最長共通部分列問題 (S と T : 共通部分文字列の最大値)
dp[S : i番目][T : j番目] = 共通部分文字列の最大値
最小コスト弾性マッチング問題 (各ペア(a,b)をマッチ : 最小コスト)
dp[a : i番目][b : j番目] = 最小コスト
レーベンシュタイン距離 ((変更、削除、挿入) s → T 変換の最小回数)
dp[S : i番目][T : j番目] = 最小回数