プログラミングコンテストチャレンジブック 第2章 その4

第2章後半「動的計画法」を読みます。

• 2-3 「動的計画法」
  • なんか動的計画法自体の説明になっていないような…
  • 01ナップサック問題
    • メモ化
  • 最長共通部分列問題
    • 連続していなくても順番が一致していればいいというのが特徴的
  • 個数制限なしナップサック問題
  • 01ナップサック問題その2
    • より計算オーダーの制約が厳しい
    • 「価値に対する最小の重さ」について DP する
  • 個数制限つき部分和問題
    • i番目までで j を作る際に余る最大のiの個数について DP
  • 最長増加部分列問題
    • a[i] が最後である増加部分列の最大の長さ
  • 分割数
  • 重複組み合わせ