7K12 blog

猫でも分かる何か

フィボナッチ数列の計算ライブラリ(メモ化再帰のテンプレート)

フィボナッチ数列の計算(メモ化再帰のテンプレートとしても使える)

#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,