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
17
#define loop(x, start, end) for(int x = start; x < end; x++)

void fib(vector<int> &dp, int n) {
    dp[0] = 1;
    dp[1] = 1;
    loop (i, 2, n+1) {
        dp[i] = dp[i-1] + dp[i-2];
    }
}

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