__spam's blog

Need help how can I convert recursive dp to iterative dp?
By __spam, history, 3 years 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

Comments Comments (4)
| Write comment?
»
3 years 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

→ Reply
  • »
    »
    3 years 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.

    → Reply
»
3 years 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.

→ Reply
»
3 years 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

→ Reply