19.30's blog

Struggling with Iterative DP
By 19.30, history, 4 hours ago, In English

I have been solving DP problems for a while now, and while I feel somewhat comfortable with recursive DP and LeetCode-style DP problems, and I have been practicing recursive DP since I started learning DP. I find myself struggling with iterative DP as well as Codeforces-style DP. Converting a recursive DP approach into an efficient iterative solution feels hard to me.

Which steps should I take to overcome this problem?

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

If I'm being honest, there's only one thing to overcome: consistent practice. If you haven't solved the CSES DP problems yet, head over to the CSES DP section and work through all 19 problems using both recursive and iterative approaches.

→ Reply
»
4 hours ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

I was in the same position a week ago, but now I'm comfortable with Iterative DP.

  • I resolved all the CSES DP problems in an iterative manner and the first 10 problems in the Atcoder DP contest.
  • Solved USACO DP problems (https://usaco.guide/gold/knapsack ).

I don't know what happened, but now I'm very comfortable with Iterative DP.

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

    I have solved most of the CSES and Atcoder DP contest problems using both recursion and iteration. But doing iterative as like converting recursive solutions to iterative to me.

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

They're both pretty much the same, after a point you'll be able to write the iterative one naturally(although I still prefer using the recursive one whenever I can)

→ Reply