Perl, 7s. Looks like I arrived at the same recurrence that madars used, but I swear I didn't look at his solution...

Memoize magically turns it from exponential to polynomial.