ritik_patel05's blog

Help in DP Problem 4D
By ritik_patel05, history, 5 years ago, In English

Problem: https://mirror.codeforces.com/contest/4/problem/D

Solution: https://mirror.codeforces.com/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 :)

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But can you tell, why my memoization is not considering all cases. It would really be helpful.

    Thank you.

    → Reply