[LANGUAGE: Go]

Definitely the most challenging problem of this year (so far). Initially I didn't even know how to go about it. I was burnt out already when I had started it and the complexity of the problem statement did not help either.

The key to coming up with a solution that scales well for part 2 lies in doing the one thing I profoundly suck at... discovering subproblems. If you can discover subproblems, you can come up with a recursion. The recursion alone will get you through part 1, and implement a little cache over it and you have the part 2 solution as well.

Here's the solution for both parts. Huge thanks to Willian Y. Feng for his video solution, explained his approach really well and nudged me in the right direction.