sonu007's blog

how i start practicing on dp and graphs problems.
By sonu007, history, 8 years ago, In English

i had read topcoder tutorial for dynamic programming but i am unable to understand state or much more please anyone help me.

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I read it too and I didn't understand much either, so I started to solve basic dp problems and then I was in the right way, and progressing with dynamic programming.

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

    on which judge i practice

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

      I remember that my first dp problems where in uva, but there is plenty of good dp problems here in codeforces, just make sure at the beginning you pick the most basic ones.

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

DP is something that requires a lot of experience in order to become good at. I recommend starting off with problems here on CF. If you are new, try to avoid problems that also have tags relating to graphs and strings. You should practice later on, but not now because the skill set required for those problems is quite different from normal DP, and you need to grasp the basic idea of DP first. As mentioned in the title, I assume that you want to learn about DP on graphs also. The most common type of DP with graphs is DP on trees. There are many great problems here on CF, which you can easily find by using the tags "dp" and "trees". There exists some very interesting DP + graph problems that are not on trees, but these are generally quite hard to find (correct me if I'm wrong). The only one I can think of right now is 645D - Robot Rapping Results Report, which is a DP on DAG.

→ Reply