Isn’t this a recursion ques? because we are either inc i to i+1 or j to j+1, so we won’t be able to find it in dp array. Correct me if I’m wrong. Thanks
Valentine Magic
hello @himanshugupta8
yeah the question has recursive nature.
the problem has overlapping sub problems so dp array will definelty save some time.
for example->
(i,j) -> (i+1,j) -> (i+1,j+1)
(i,j) -> (i,j+1) -> (i+1,j+1)
u can see there are more than one way to reach to particular state hence there is overlapping of subproblem hence we should use dp array
no dp right??..
it is dp , that is what i proved above.
it has overlapping subroblems
yeah, I got it. Thanks again
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.