Is the complexity of this code is O(n^2) in worst case? and if so how DP is applied here then…like DP is used to optimize the code complexity…
Longest Increasing Subsequence Code
@archa_1712
Yes we optimised the brute force solution which was to generate all subsequences and then check if it is increasing or not. which was (2^n) * n .
Dp is not about optimizing, It is about avoiding over calculation. If you are doing same calculation a number of times, Dp saves the state and help us avoid over calculating things. Doing so, it does optimizes the code.
So yea we optimised (2^n)*n to n^2 that is a very big optimisation.
And about how dp is applied here :
When you are at the i’th element,you used the answers from 0 to i-1 to calculate dp[i]. That is optimal substructure property which is necessary for DP.
So the approach in the video is the bottom up approach…i think so…and how the top down approach will be applied here?
@archa_1712
Here is the top down version. I strongly feel you should try to think about it before opening the link. If you know bottom up approach you should be able to convert it to top down.
okay i am going to try it…and one more thing…in top down approach there will be always memoization?
Yes. To avoid over calculation we memoize it.
so top down approach will be always a recursive based soln?..
Yes. …
okay . … …