Variant 1 - Solve the same problem using O(s) space
How do you reduce space of the Cache? Any Ideas?
Examine the way you use the contents of the cache in your code. At each step, when computing the cache, do you really need ALL the previous rows and columns? Is there some way to limit what’s kept in the cache to just what’s needed?