I_am_Vengeance's blog

Space Optimization in recursive DP?
By I_am_Vengeance, history, 4 years 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

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

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

    → Reply
    • »
      »
      »
      4 years 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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        both.

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

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

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            That's why, I said most of the time

            → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        I like recursive dp!

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

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

→ Reply