My first attempt was a recursive solution without memoization, which I suspected would not pass all leetcode test cases and it didn’t. I then modified this to use memoization, which saved doing the same calculations over and over again.
Here is the code without memoization:
https://gist.github.com/adamkorg/5cee9720741ec9cbe9f83ba2391f99b8
And here is the code with memoization: