_abhijit_'s blog

Dynamic Programming States and Recurrence Relation
By _abhijit_, history, 4 years ago, In English

Hello Codeforces Community!

I am trying to get better at dynamic programming. During live contests I am able to identify a dp problem but unable to come up with the particular states which define/uniquely identify a sub problem and also I find coming up with a recurrence relation is a tough task. I find it magical how many people have mastered this concept and are able to come up with the dp states and recurrence relation within a matter of minutes. I'm not able to overcome this. It would be helpful if you could share some insights to get better at this (If possible please share your thought process during the contest). Also, it would be helpful if you could provide some common dp states/problems which are typically useful to solve Div2 C & D problems.

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

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

+1 from my side . please guide us.

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

Practice!

Really, that's all there is. Just ask yourself "what info do I need?" If you do it enough, you'll be able to do it better (partially because a lot of DP states are somewhat similar).

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

Knowing how to do many of the classical DP problems can help you come up with many new ideas. I think that the DP section on CSES is pretty useful for an introduction to DP, and the main way that I practiced DP to learn it initially was to turn on the dp tag on the Codeforces and start at 1600 and work my way up once you feel comfortable with that rating.

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

    Ok... So for classical problems AtCoder DP contest and Can you please tell me about CSES? I've not heard about it before

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

I've had a similar problem almost a year ago, when I struggled at even the most standard DP problems. I can't say that I am as good as a div.1 participant at this type of problems, but I've improved a lot and what I can say is that practice is everything. Start with reasonably easy problems (I think 1500 rating is good), then gradually increase the difficulty. I don't think there are some common DP states, but you can usually somewhat estimate how many dimensions your DP requires by looking at the constraints of the problem. When solving a DP problem, it's important to think about how you can split the original problem into smaller subproblems.

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

Let me share my thought process of a recent dp problem: LINK

1) At each step how many options do I have? — When I am at some position $$$i$$$, I can kill $$$1$$$ monster and go to $$$i+1$$$ or I can kill $$$2$$$ monster and go to $$$i+2$$$. So $$$2$$$ options.

2) If I know the answer for both options can I find the answer for my current position? — Here the problem tells us to kill all monsters using minimum tickets. Let's say $$$A =$$$ minimum cost of killing all monsters from $$$(i+1)$$$ , $$$B =$$$ minimum cost of killing all monsters from $$$(i+2)$$$. Then what is the minimum cost of killing all monsters from $$$i$$$?
$$$ANS = min(X + A, Y + B)$$$
$$$X =$$$ cost of going from $$$i\rightarrow i+1$$$
$$$Y = $$$cost of going from $$$i\rightarrow i+2$$$.
Now the value of $$$X$$$ and $$$Y$$$ depends on whether the monsters are being killed by you or by your friend. So you need to know who is in operation right now, and that's when I realize I need another state in my dp function which will determine this. So our function will look like $$$F(i, t)$$$, here $$$i$$$ is the position you are at, and t determines if it is your move or your friend's move.

SOLUTION

→ Reply