メモ化再帰の話

2020,11,9

ABC 182 E 解説放送にてメモ化再帰を難しいと思ったので書く

とにかく例題に触れて慣れよう！

例題

• ABC182E .... グリッドが光る条件はそのグリッドの周りの4方向が光っていることにある。よって大枠として全てのグリッドを見る。1つのグリッドを見るときは、その周りのグリッドも再帰的にみる。ここで、一度見たグリッドは大枠で見たときにO(1)でreturn するため、1つのグリッドを走査する回数は高々1回となる。

大切なこと

メモ化再帰はメモ化全探索である。dpは前の状態から今の状態を作るときに使う。メモ化再帰は今の状態を作るために必要な状態をすべて確定させながら今の状態を決める。

イメージを大切にしよう。