Project Euler 709 - Even Stevens

Official link: https://projecteuler.net/problem=709

Thought Process

A bit of a scummy solution here. I manually calculated the first few obvious values, that is, f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 5, took those values and put them into OEIS and scrolled down and luckily a sequence where the 8th term was 1385, I then just assumed that this would be the correct answer.

Some scrolling through this page landed me on Entringer Numbers which are easily recursively calculated by the following relation:

As stated on the Entringer Numbers page, we have that f(n) = E(n, n) as it corresponds to the Exponential Generating Function (e.g.f) on the OEIS page

I implemented a simple dynamic programming solution as the recursion limit was hit rather quickly, my code takes about ~120s but given that I completely cheated the problem it doesn't matter much anyway

Interactive Code

Input an integer (yourinput)

Code will output f(yourinput)