DP Fibonacci atualizado

dp_fib.cpp

#include <cstdio>

const int maxn = 100010;

int n, dp[maxn];
bool mark[maxn]; // inicialmente o vetor é preenchido com 0

int fib(int x) {
	// caso base
	if(x <= 1) return 1;
	
	// Se já visitamos esse estado retornamos o valor calculado
	if(mark[x] == 1) return dp[x];
	
	// marco o estado como visitado
	mark[x] = 1;
	
	// calculamos esse estado
	dp[x] = fib(x-1) + fib(x-2);

	return dp[x];
}

int main() {
	scanf("%d", &n);
	printf("%d\n", fib(n));
}