Lookup in DP array

#1

Can we use look up in DP array here?
I think in the solution discussed, we are not reducing the repeated computations.

#2

Hey @bade585 we are definitely using the dp array on this approach so as to reduce the computations and final complexity is O(N^2). Let me explain with an example.
Let’s say we have a sequence {2,4,1,6} and I am going to use 1-based indexing for explanation here.
So dp[1] stores 1, dp[2] after comparing with dp[1] stores 2, similarly dp[3] stores 1. Now lets talk about dp[4].
While computing dp[4] ,when I compare it with dp[2], I know that dp[4] will be dp[2]+1,i.e, equal to 3 because we have already computed dp[2] and aren’t repeating the computation again to find the longest sub sequence ending at index 2.
So we are definitely reducing the amount of computations while calculating our answer with the help of dp.

#3

If you don’t have any further queries, please mark the doubt as resolved.

#4

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.