Codeforces will be possibly unavailable in the period between Sep. 19, 19:00 (UTC) and Sep. 19, 21:00 (UTC) because of maintenance. ×

__spam's blog

By __spam, history, 6 weeks ago, In English

Please give me efficient and easy way that I can covert recursive dp to iterative dp. You can suggest me blogs or video tutorial. It will be very helpful.

Thanks in advance.

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

»
6 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

Why write recursive dp in the first place? It's so confusing to write

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I learned dp in recursive way in primary level but now I think I need to move in iterative way for time and also memory optimization. But I found recursive solution for most of the problem, so I need now how can I think in iterative way.

»
6 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

First, writing recursive dp is slower but its necessary for some problems. Sometimes you just can't do it.

Now answering your question, it's mainly about what states need to be calculated before you can safely calculate the current one. For example if you're doing a 2d knapsack like dp[i][j] — being i the item and j the value — for each item you need to calculate the items that go before it first, so you iterate through i from 1 to n. At that point, it's just the same as a recursive dp, but you are accessing the array instead of calling a function.

In this case it's simple (actually most cases are simple) but sometimes you will need to think a little bit. For example when dp[i][j] means a segment from i to j and it depends on dp[i][k] and dp[k][j] (that is, a dp of intervals where to calculate it you use the dp of smaller intervals), you will need to iterate through the length of the segment instead of something else.

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

you can always use a stack like data structure to convert any recursive function to an iterative function

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.youtube.com/watch?v=ntCGbPMeqgg&list=PL_z_8CaSLPWekqhdCPmFohncHwz8TY2Go&index=5 This is gem , if you can understand Hindi , watch this and previous 2 videos and you will be good !!

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just think of every state as a small recursive problem. For example in the Knapsack Problem , if you have n items then lets say for the last item you have two choices ,you take it or dont take it . Now if you take it then you call the recursion again by reducing the size 1 and subtracting the weight from knapsack (func(n-1,W-wt) ) , second condition if you dont take it then you call the recursive function by not taking the item and thus not subtracting an value from knapsack (func(n-1,W)). Same happens in the iterative code , let the there be i items and weight of knapsack be j then if you take last item then dp[i-1][j-wt[i-1]] , if you dont take the last item dp[i-1][j]. I am a beginner ,if got anything wrong in here then correct me. Thanks