copycat69's blog

DO YOU USE ITERATIVE DP??
By copycat69, history, 3 months ago, In English

I'm learning DP . Most of the code I've seen so far uses iterative DP. Is there anyone who uses Recursive DP?????

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

»
3 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Recursive dp usually has a lot of overhead time and memory-wise since recursion requires a call stack in memory and sometimes that exceeds the time or memory limit.

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

I use recursive DP when I am unsure in order of computing(or a lot of parameters). If it TLs then I rewrite it on iterative(if it is possible).

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

recursive dp sucks

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

I've seen many blog and comments saying iterative DP is better in many ways.... How do you get better at iterative DP ? I mean you need to be good at Recursive DP first R8?

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Though I am not very good with dp, i find iterative dp easier than recursive dp (maybe coz i am not that good with backtracking)

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

recursive is more intuitive for me. Sometimes I'm forced to write iterative anyways though.

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

I use iterative DP & now it's a lot easier to think in iterative way.

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

As someone who codes Python too often, I'm immensely scared of whatever being recursive.

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

It's OK to use recursive DP when learning DP. recursive DPs can be easier to understand when first learning DP because the relationships between states are more obvious to see. I mostly used recursive DP until I became purple.

→ Reply
  • »
    »
    3 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    how did you transition? I mean it's quite difficult to transform recursive dp thinking to an iterative one. Are there any tricks you use to develop this skill or do you first solve recursively then transform the solution to an iterative one?

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

      Idk I did suffer when I first tried to use iterative DP instead of recursive ones.

      At some point iterative DP felt more comfortable than recursive DP.

      it's just magic. you try to use iterative DP and someday when you look back you are only using iterative DP.

      → Reply