Boring_Day's blog

There are always some issues while solving problems with recursive dp.
By Boring_Day, history, 22 months ago, In English

As we can see that some people have habit of directly using recursive dp even for the easiest of the problems. But it becomes very problematic. You can't solve problems in which you need to save memory by knowing the previous row, and also in some prolems like recent E "Sum over zero" where you will face some issue related to time and memory. And i don't think it's possible to solve it with recursive dp. So i would suggest you guys to solve problems with iterative dp. Make a habit of using iterative dp. It will be beneficial for you guys in future.

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

Comments Comments (3)
| Write comment?
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Moreover iterative dp is easier to debug!

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Iterative DP is harder to come up with than recursive DP. It's good to practice both, but in a contest when it is possible to solve using recursive DP use it, when it's not try to find the iterative.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Some things that I picked up while solving different DP problems:

  • It is always a good idea to first think of recurrence relation than order in which the states are calculated for any DP problem.
  • Some problem requires memory optimization, which is very hard to implement in a recursive solution. CSES — Book Shop (if you have a recursive solution for this do share)
  • If you are comfortable with recursive DP then code it and then convert it to iterative (not that hard of a job once you get use to it). Examples: Problem: Leetcode — Predict the Winner First Code: recursive solution Second Code: recursive solution to iterative solution
  • Bonus: I used lambda function in my recursive solution which makes it easy to code instead of declaring stuff globally or passing everything by reference. (At the end of the it depends on your style of programming)

Some questions:

  • Can someone suggest some good video resources to learn DP optimizations (like convex hull, 1D1D, etc)?
→ Reply