Memoization

Memoization caches the return value of a function for each unique input, converting exponential recursion to polynomial time. Use a Dictionary<(int, int), int> or a 2D array. Identify the "state" (all parameters that uniquely determine the result) to design the cache key.