概念 / メモ化

同じ部分問題を
何度も解かない。

再帰で同じ計算を繰り返すと急に重くなります。メモ化は、一度求めた結果を保存して再利用する方法です。

再帰の高速化同じ入力を再計算しないDP の入口

このページの目次

このページでわかること概要最小形要点まとめ動きで確認次に見るページ

このページでわかること

先に知っておくポイント

1. 重複している部分問題を探す

2. 保存して使い回せる値を見つける

3. 再帰木がどれだけ減るか見る

概要

再帰で同じ計算を繰り返すと急に重くなります。メモ化は、一度求めた結果を保存して再利用する方法です。

考え方

最小形

if メモにあるなら返す
なければ再帰で求める
結果をメモに保存する
保存した結果を返す

要点

要点まとめ

テーマ

横断概念

典型例

Fibonacci

効果

重複計算の削減

接続

Top-down DP

補足

向いている場面と注意点

なぜ効くか

同じ引数で同じ結果が出るなら、2回目以降は再計算不要だからです。

授業の見せ方

メモなしの再帰木と、メモありの計算済み表を並べると差が出ます。

注意点

保存領域を使うので、空間計算量とのトレードオフがあります。

動きで確認

動きを見てたしかめる

ここでは「重複している部分問題を探す」を見ながら、上で読んだ内容を動きと結びつけます。

未計算計算中メモ済み

次に見る

次に見るページ

比較すると違いがわかりやすいページを先に置いています。

トップへ戻る

同じ部分問題を何度も解かない。