How does complexity get reduced to O(n^2) from O(2^n) in case of memoization?

When memoizing a function, you make a note each time you call that function of a) the parameters and b) the result. Then next when you want to call the function again, you check in your notes whether you've called that function before with the parameters you want to use this time. If you have, you don't need to call the function again, because you already have the result. This way the function is called only as many times as you have distinct parameters: if you want to call it with parameters you've used already, you save having to call it.

This approach works well where a) the function is deterministic, i.e. returns the same value each time it is called with the same paramters, and b) the function is expensive compared to the cost of memoization.

The example you cite says this:

In the previous approach, many recursive calls had to made again and again with the same parameters. This redundancy can be eliminated by storing the results obtained for a particular call in a 2-d memorization array

Here the function in question is called O(2ⁿ) times, but with only O(n²) different sets of parameters. Using memoization, the function is called once only for each different parameter set (O(n²)) rather than each time the algorithm needs the answer (O(2ⁿ)).

Here is a reference which may help.

I guess the answer is given in the link provided by you in the question only! I will quote it from there as it is:

"for a particular call in a 2-d memorization array memomemo. memo[i][j]memo[i][j] represents the length of the LIS possible using nums[i]nums[i] as the previous element considered to be included/not included in the LIS, with nums[j]nums[j] as the current element considered to be included/not included in the LIS."

I assume that you have understood the first solution of recursion and then moved to this solution, So by now you would have understood the basic concept of what we were trying to do in that first solution: we were checking whether we get maximum either by including or excluding the current element of array. Thats why we were making 2 calls everytime, one by taking current element as prev and other by keeping prev as it is(of course we were taking other parameters of function appropriately too!). Due to this approach it was taking O(2^n).

so if my prev = n-2 and cur = n-1 then I can either exclude n-1 or consider n-1 in counting LIS. our function calls would look something like this:

                                prev=n-2,cur=n-1
            prev=n-1, cur=n                        prev=n-2, cur = n
prev=n-1, cur=n+1        prev=n, cur=n+1     prev=n-2,cur=n+1     prev=n,cur=n+1

So it is clear that we will unnecessarily call function with prev = n and cur = n+1 twice and all descendants calls will also be called twice! So the key idea here is to use the memorized answer directly and thereby eliminate all descendants function calls

another example with array = [1, 2, 3, 4]

                                        min_int, 1

                min_int, 2                                  1, 2

    min_int,3                   2, 3                1, 3            2, 3 

 min_int, 4  3, 4       2, 4    3, 4          1, 4     3, 4    2, 4    3, 4

here 2,3 call is done twice, this example is not very efficient as array size is small, but I hope you got my point that we are reducing complexity exponentially as we are eliminating subsequent function calls.

So how many calls can there be? approximately we can think of answer as: each element can be there at prev and current parameter so there can be approximately O(n^2) possibilities and we were over-counting them!