Here is a small memoized recursive solution in Python [1]. It's pretty quick.

[1] https://gist.github.com/pavelb/1d62e81b35d18fc1441ea59361b54...