The_mysterio's blog

A bit of discussion on DP
By The_mysterio, history, 3 years ago, In English

Hello community, We all know that the 2 properties for a DP problem are 1) Overlapping Subproblems 2) Optimal Substructure . So, when we start doing DP problems, many like me first try to find out whether the problem can be solved recursively and if so does it have overlapping subproblems. But doing this during a contest takes a lot of time. People who are able to comfortably solve DP problems during a contest, do you guys really check these two patterns , whether they exist in the problem or do you look for any other insights??

Thank you if you choose to reply in the comments

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Formulating DP fast comes with experience, there is nothing more to it.

Also, I have no idea what "overlapping subproblems" and "optimal substructure" mean. Well, I can guess based on the paragraph after but it still sounds very strange.

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Sometimes for me, problem constraints are the biggest hint for DP :)

→ Reply