Problem: https://codeforces.me/contest/4/problem/D
Solution: https://codeforces.me/contest/4/submission/73546246
What I am doing is first sorting indexes with given height and width in increasing order. Then I am making a recursive function to calculate longest chain. Whenever I reach an index, I have 2 options either include or don't include it.
I have been trying to find for long why am I getting the wrong answer. But I have no clue.
It would be great if someone could point out my error in thinking.
Thank you :)
Hi ritik, Your memorization is wrong as you are not going to all possible combinations. Give look at my solution. This question could have done using 2D dp states — (current_idx,lst_picked_idx) but the memory constraint are bad.
But can you tell, why my memoization is not considering all cases. It would really be helpful.
Thank you.