Taha1506's blog

How to recognize "Standard dp" problems
By Taha1506, history, 3 years ago, In English

Some time ago someone told me that when your choices are quite dependent to each other then using dp will be a great idea having this in mind it helped me to come up with the dp idea in a lot of problems in the first place.Yesterday I saw a problem that had dp solution see the link .I wasn't able to recognize it is a dp problem until the end of the contest.But a yellow coder seeing the problem in the first place told that it is a standard dp problem.So my question is how to recognize "Standard dp" problems?Can anyone tell me what property of the problem makes it a standard dp problem?Thanks in advance.

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

»
3 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

I think that: A property of a standard dp problem is such the problem that is a simple, well-known, well-discussed problem that can be solved with dynamic programming and having a lot of research, tutorial videos, papers about it as its wonderful applications. So it can be recognized when we observed many problems solved have the same pattern of a simpler standard dp problem.

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

    having a lot of research, documentaries, papers about it as its wonderful applications

    I'd love to watch some dp documentaries

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I'd love to watch some dp documentaries

      :VVvvv oops, sorry for my poor English, edited to tutorial videos

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

$$$n \leq 100$$$ and $$$a_{i} \leq 100$$$ suggests dp. Looks too big for bitmasks and meet in the middle and too small for most other standard cp techniques.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    there are a multitude of questions with large $$$N$$$ that are still solvable with DP. it's more about whether you can turn the question into states or subproblems.

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

Coding problems asked in company interview's are "standard dp".
On a serious note: Dimension is the only way i recognise dp.

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

Even i had the same question in my mind . I am mostly accustomed to solving dp problem that are standard and you can figure the dp states from the question itself. But this is different type of dp problem. Hope to solve more of such problems .

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +70 Vote: I do not like it

Standard problems are recognized by having experience. Looking at constraints and forcing DP is dumb.

→ Reply