動的計画法n本ノック

動的計画法n本のノック
問題の種別ごとにまとめてく(作成中・・・)

基本問題1

  • 状態空間が1次元配列で表すことができ,遷移も比較的単純なもの
フィボナッチ数列
コイン支払い問題
最大部分列和問題
部分和問題
その他

基本問題2

  • 状態空間が2次元で表すことができ,遷移も比較的単純なもの
ナップサック問題
コイン両替問題

桁DP

木DP

BitDP

巡回セールスマン問題

確率・期待値

ゲーム

文字列

最長共通部分列問題
最長増加部分列問題
編集距離

区間DP