メモ化再帰(コピペ用)
(library/dp/dfs_memo.hpp)

• View this file on GitHub
• Last update: 2026-03-13 12:01:35+00:00
• Include: #include "library/dp/dfs_memo.hpp"

メモ化再帰

できること

• メモしながら再帰する

行きがけ/帰りがけの順はこちらを参考

計算量

$O(NlogN)$

使い方

コピペして使う

Code

#pragma once
// メモ化再帰 !!コピペ用!! 関数内をペーストして書き換えて使う
void dfs_memo() {
    map<int, int> memo; // メモ
    auto dfs = [&](auto f, int n) {
        if (n <= 1) return n;                       // ベースケース
        if (memo.count(n)) return memo[n];          // メモにあれば採用
        return memo[n] = f(f, n - 1) + f(f, n - 2); // メモしつつ、再帰して計算
    };
    (void)dfs; // unused
    // int ans = dfs(dfs, N);
}

#line 2 "library/dp/dfs_memo.hpp"
// メモ化再帰 !!コピペ用!! 関数内をペーストして書き換えて使う
void dfs_memo() {
    map<int, int> memo; // メモ
    auto dfs = [&](auto f, int n) {
        if (n <= 1) return n;                       // ベースケース
        if (memo.count(n)) return memo[n];          // メモにあれば採用
        return memo[n] = f(f, n - 1) + f(f, n - 2); // メモしつつ、再帰して計算
    };
    (void)dfs; // unused
    // int ans = dfs(dfs, N);
}

Back to top page