フィボナッチ数列の計算(メモ化再帰のテンプレートとしても使える)
#include <bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; auto mf = [&](auto self, ll now, vl& memo, ll inf) -> void { if (now == 1 || now == 2) { // 末端は定数 memo[1] = memo[2] = 1; return; } // 未計算なら潜る if (memo[now - 1] == inf) self(self, now - 1, memo, inf); // メモを使って計算 memo[now] = memo[now - 1] + memo[now - 2]; };
使用法
int main() { ll N = 10; vl memo(N + 1, inf); mf(mf, N, memo, inf); for (ll i = 1; i <= 10; i++) cout << memo[i] << ","; return 0; }
1,1,2,3,5,8,13,21,34,55,