szawinis's blog

By szawinis, history, 8 years ago, In English

From my perspective, I feel like many DP problems are really hard to code and easy to bug out, especially when there are many dimensions and you have to check the upper and lower bounds for each of them. Also, I find that when debugging DP problems with many dimensions, it becomes very tedious and the printing format gets very messy, which makes it really hard.

This particularly caused me to fail in the last round (369), since I couldn't get my code right on C, Do you guys have any tips on how I could improve?

Also, for a slow coder like me, would you recommend iterative or recursive DP? Which is easier and faster to code?

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

»
8 years ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

Recursive dp is always easier because it comes directly from the recurrence that describes the target function to be optimized by dp, sometimes it's not fast enough or the recursion depth can cause stack overflow, but usually the recursive solution is ok.

To get better, the only tip i can really give is to practice a lot, after you have solved hundreds of dp problems you have a lot of patterns in your mind, and solving one more problem becomes much easier. The hardest part is describing the target function states and transitions, and when you have it, it's just a matter of adding the memo tables to optimize the function.

EDIT : i forgot to say that sometimes you need to code the iterative dp because you have to use some optimization like convex hull trick or fast range min query, but this kind of problem is kinda rare and more likely to appear as problem E on div 2 round

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    You don't need to solve "hundreds" of dp problems. about 50/60 different problems should be enough to make almost all not unique problems.