wish_me's blog

By wish_me, history, 6 years ago, In English

I was trying to solve the problem http://codeforces.com/problemset/problem/380/C .I saw Segment tree approach in the editorials.Now I was thinking Can we do it by memoization.Increasing the value +1 for every "(".Now we have two options ,Whether we should include next character to close this subsequence on not.Initially it would be exponential but by doing memoization I think we can do this.Looking to hear from you guyz?????

Tags #dp
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I suggest you to take some time to fully understand about time complexity

How are you going to solve this problem using DP given those constraints? If you are going to just bruteforce on the query segment [l, r] it will take you O(n) per query giving you a O(mn) solution in the end. And talking about memoization, you are storing the answer for every [l, r] segment, which ends up using O(n2) memory and time complexity, by the end of the day you just get a O(mn2) solution (even worse than bruteforce xD)