please explain me how to calculate the time complexity of recursive wine DP problem…ie. O(2^n)…i didnt get it how it came?
Wine problem with recursion time complexity
In top down approach , at each level or each you are making two recursive calls , so at every level there will be 2 raise to power level call , so for n level the complexity will be O(2^n).
But if you use memoization then you dp state only depend on two factors , first position and last position ,
So your complexity will goes O(n^2).