Блог пользователя code_kika

Автор code_kika, история, 8 лет назад, По-английски

Recently, I learnt about DP and started solving problems related to it. When I know the problem is on DP and then when I solve the question, I am surely able to find the recurrence relation, but when not specified, I am finding it difficult to identify whether the problem is on DP or not. How to distinguish whether a problem is on DP or greedy or ad hoc? And can somebody also provide links of good problems involving DP.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by code_kika (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Like in all other problems you should try different approaches. You said that if you know that the problem is DP then it is easy for you to solve (probably you haven't seen really hard DP problems). Try to assume that problem is DP. If you can figure out the solution in 10 minutes (or 15, or whatever) then... you solved the problem, great. If you cannot then maybe it is not DP? You cannot be sure but it is better to try something else.

Knowing some famous DP problems might be helpful. If you see a knapsack problem with some additional constraints then the solution is probably like in a knapsack problem.