Блог пользователя __spam

Автор __spam, история, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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