Dynamic Programming States and Recurrence Relation

Revision en1, by _abhijit_, 2020-09-29 20:07:03

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.

Tags #dp, #dynamic-programming

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English _abhijit_ 2020-09-29 20:07:03 828 Initial revision (published)