I_am_Vengeance's blog

By I_am_Vengeance, history, 6 weeks ago, In English

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?

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

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

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

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

      Do you prefer recursive dp because you are noobs or are you noobs because you prefer recursive dp?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        both.

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

        Ashishgup prefer recursive dp most of the time and he is definitely not a noob.

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

          Its just because recursive is slower than iterative and requires more memory in some cases where you are initializing any container. If you see these problems even Ashishgup used recursive first and then commented that part out 36262262.

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

        I like recursive dp!

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

    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.

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

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.