About the time complexity of wines dp prblm

#1

why is the time complexity of the top down approach of the wines dp prblm is O(Nsquare)?

#2

Hey @Senjuti256
Upon every recursive calls, there are two possibilities, ie either pick the present first wine or present last wine! which gets to O(2^n)!, but with memoization, it becomes O(n^2) only which is number of distinct states

#3

Why the no. Of distinct States is n square?

#4

See
There is an array
And u can either remove first or remove last
So basically u are making calls for leftout array (i,j)
And here both can take n values so n*n =n^2

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.