Simple way to understand through tree


#1

Suppose the function is called on (1,1). Now, When we don’t use memoization i.e., storing the results of already calculated cells, this will be the recursion tree.


As u can see it contains lot of redundant calls denoted in circles.

When we use memoization then these redundant calls are eliminated because we do not need to recompute them, we already have them as a result and hence, we just need to go on every cell once which makes the time complexity of memoiztion code to be O(R*C) instead of exponential