トップダウン
個々の問題を上から順に計算していく分割統治法の手法。
再帰関数を用いたアプローチで、高速化にはメモ化を使う。
フィボナッチ数列をトップダウン型の動的計画法を用いて計算する例。
code:fib.cpp
#include <bits/stdc++.h>
using namespace std;
ulong fib(vector<ulong> &a, int n) {
if (an != -1) {
return an;
}
an = fib(a, n - 1) + fib(a, n - 2);
return an;
}
int main() {
const int N = 40;
vector<ulong> a(N + 1, -1);
a0 = 0;
a1 = 1;
for (int n = 0; n <= N; n++) {
cout << "n=" << n << ": " << fib(a, n) << endl;
}
}