日記

のみろぐ

主に競プロ日記です

DPログ

  • 解いたDPの解説記事を列挙していきます
  • 逐次更新
  • DP問題投げてくれると嬉しい

1次元DP


2次元DP


メモ

  • DPの本質はあるポイントに値を収束させることの繰り返しである(集めるDP)。
  • $dp[i]$を計算するとき、$dp[i-1]$までは計算済みであることが前提となっている。なので、$dp[i]$を求めるときはそれ以前がどういった状態であるかを考える必要は無い。このへんは結構シンプルな気がする。
  • DPで解こうとするときに大事なことは、最初にDPをするために必要な情報を考えてDPテーブルを作ることだと思う

DPの流れ

  1. DPテーブルを作る
    • 答えを求めるために必要最小限の情報を考える
    • 余計な情報はいらない
  2. DPテーブルを初期化する
  3. 漸化式を立てる
  4. コードを書く