メモ化再帰 dynamic-programming メモ化

メモ化再帰

メモ化再帰
Feb. 2, 2020, 1:51 p.m.

目次

一度計算した部分を配列に保存しておき2回目以降は計算を省略する高速化手法を動的計画法という.

その中でも計算をトップダウンに分解していき、途中で出会った計算をその都度配列に保存していく手法がメモ化再帰.

コピー&ペーストで動作するサンプルコード

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
int fib(vector<int> &dp, int n) {
    if (n == 0 || n == 1) {
        return dp[n] = 1;
    }

    if (dp[n] > 0) return dp[n];

    return dp[n] = fib(dp, n - 1) + fib(dp, n - 2);
}

int main(void){
    int n;
    cin >> n;
    vector<int> dp(n+1);
    cout << fib(dp, n) << endl;
}