#include "s0509_fibonacci_number.hpp"

int S0509::fib(int n) {
  vector<int> dp{0, 1};
  for (int i{2}; i <= n; ++i) {
    dp.push_back(dp[i - 1] + dp[i - 2]);
  }
  return dp[n];
}