0Pricing
Competitive Programming Academy · レッスン

メモ化と tabulation の比較

部分問題の答えをキャッシュする 2 つの方法を学びます

「メモ化と tabulation の比較」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

なぜキャッシュするのか

素朴な再帰では、同じ処理を何度も繰り返します。動的計画法では各答えを1回だけ保存するため、再計算せずに済みます。

fib(40)  # slow: recomputes endlessly

重複する部分問題

問題が重複する部分問題に分割されるとき、DPを適用できます。再帰の多くの分岐で、同じ小さなケースが現れます。

fib(5) needs fib(3) twice

トップダウン：メモ化

メモ化は、キャッシュを加えた通常の再帰です。必要になったときに計算し、各入力を初めて処理したときの結果を記憶します。

memo = {}

Pythonで簡単にメモ化する

lru_cacheデコレーターを使うと、1行で遅い再帰を高速なDPに変えられます。すべての呼び出しが自動的にキャッシュされます。

from functools import lru_cache
@lru_cache(None)
def f(n): ...

ボトムアップ：表計算

表計算では、最小のケースから答えに向かってテーブルを埋めます。再帰の代わりにループを使います。

dp = [0] * (n + 1)

表計算によるフィボナッチ数列

基底値を設定し、各セルからすでに計算された値を参照します。コールスタックは不要で、すっきりしたループだけで済みます。

dp[0], dp[1] = 0, 1
for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

同じ答え、異なる方法

メモ化と表計算は同じ漸化式を解きます。違いは方向だけです。トップダウンで必要なときに計算するか、ボトムアップで順番に計算するかの違いです。

メモ化を選ぶ場面

漸化式を自然に書け、すべての状態を計算する必要がないかもしれない場合は、メモ化を選びます。

表計算を選ぶ場面

処理を高速なループにしたい場合、再帰制限エラーを避けたい場合、またはいずれにせよテーブル全体を計算する場合は表計算を選びます。

import sys; sys.setrecursionlimit(10**6)

再帰制限に注意する

深いメモ化再帰では、Pythonの再帰制限に達し、大きな入力で実行時エラーになることがあります。

どちらにも共通するコスト

どちらの方法でも、高速化の理由は各状態を1回だけ解くことです。合計時間は、状態数と状態ごとの処理量の積になります。

確認問題

ループを使ってボトムアップにテーブルを埋める方法はどちらですか？

まとめ：2つの道、1つのDP

部分問題をキャッシュする方法は2つあります。メモ化はトップダウンで再帰し、表計算はボトムアップでループします。読みやすい方を選びます。✨

よくある質問

「メモ化と tabulation の比較」レッスンは無料ですか？

はい。「メモ化と tabulation の比較」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「メモ化と tabulation の比較」で何を学びますか？

部分問題の答えをキャッシュする 2 つの方法を学びます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

「メモ化と tabulation の比較」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. メモ化と tabulation の比較
  2. 状態と遷移を定義する
  3. 階段登りとコインの組み合わせ
  4. 最長増加部分列
← Competitive Programming Academyに戻る