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

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

Is there any way to space optimize a recursive DP for example say the 0-1 knapsack problem where we can do it iteratively using a 2xN dp array iteratively. Recently I came across this probelem and this problem where I was forced to use an iterative DP. Is there any way to solve these problems recursively?

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

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

Why don't you like the iterative approach? It will already have O(n) memory. You won't have any recursion that uses less than O(n) memory here.

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

    I think it's not about liking or disliking . I just find that iterative dp is a bit hard to implement than the recursive dp . So noobs like me generally prefer recursive dp .

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

    Recursive dp is just more intuitive to me, and it's the first solution that comes to my mind. Converting it to iterative takes a bit of time and is confusing for me if it contains more than two states.

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

Most of the time it's not possible to do such space optimization(unless you are removing a state from recursive dp approach which is dependent on other and can be derived from other states) in recursive dp.
Sometimes, it can be helpful in reducing time complexity in some cases where all the states need not to be calculated(because iterative dp calculates all earlier states and then only moves forward). An example of such a problem is this.