Longest Increasing Subsequence

#1

problem


why I can’t memoize my code only on basis of the index state where standing rather than memorizing the prev element state too ?
my code

#2

Only bottom-up approach is used to solve this question. We never use a top-down approach for this.

#3

bhaiya TLE to aaye it is giving wrong answer

#4

Yeah wrong hi dega
Bottom-up approach se try kro

#5

bhaiya this is quite absurd I wrote a solution which is following an algo 20 test cases are getting passed and I am asking u for help to debug it but u r saying change ur approach !!! just like don’t repair the faulty mobile just change it

#6

I am not asking you to change your approach. You will be using dp only. But there are some questions that follow a specific method and are done in a particular way, for easier understanding.
I have never seen if anyone has ever done/taught this question using top-down approach.
Btw, you are getting wrong answer for the sample test case only. Did you try dry running your code on that? (On paper)

#7

trying it recursion tree is too big

#8

image
image1920×1080 256 KB

Two parameters are changing your in recursive function. So ideally, a 2d dp should be used. Now we are getting TLE.

#9

You can refer to this article: https://stackoverflow.com/questions/37561909/does-there-exist-a-top-down-dynamic-programming-solution-for-longest-increasing

If you are still not satisfied, maybe a google search can help!

#10

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.