I went down some time consuming dead ends on this problem. I focused on combinations and binomial coefficients. But these suffered from number variable overflow. What I initially missed was that the results of each n follows a fibonacci sequence. It is easy once you realise that.
![](https://www.adamk.org/wp-content/uploads/2019/10/whiteboard-leetcode70a-1024x768.jpg)
![](https://www.adamk.org/wp-content/uploads/2019/10/whiteboard-leetcode70b-1024x768.jpg)