how is the top-down approach time complexity O(n^2)?
and bottom-up code is not there in the video?
Wines problem ? implimentation
As you can see that your recursive function is dependent upon two variable , i & j so that’s why it will compute a n X n matrix . though resulting in O(N^2)
It might be in some other video of your course content of DP only. If not there. Then you have to build your own solution for Bottom up code.
Hint: Think it iteratively by performing operations on dp matrix of position i,j as you saw in top down approach.
if there are two variable ,I and j .so,what ? why time is o(n^2) ??
We will use the 2-D array to store the profit for a particular year, initially, all the profit from the sale is zero. For memoization, we will use the start and end state. If the dp[start][end] is equal to zero it means we haven’t solved for that year and if the dp[start][end] is not equal to zero then that dp[start][end] is returned. Also you will do 2 recurive call, bu calcuating profit whn you pick from start and end. So your problem will be in O(N^2) time complexity.
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.