### I_am_Vengeance's blog

By I_am_Vengeance, history, 2 years ago,

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

| Write comment?
 » 2 years ago, # |   +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.
•  » » 2 years ago, # ^ |   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 .
•  » » » 2 years ago, # ^ |   +25 Do you prefer recursive dp because you are noobs or are you noobs because you prefer recursive dp?
•  » » » » 2 years ago, # ^ |   0 both.
•  » » » » 2 years ago, # ^ |   +18 Ashishgup prefer recursive dp most of the time and he is definitely not a noob.
•  » » » » » 2 years ago, # ^ |   +3 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.
•  » » » » » » 2 years ago, # ^ |   +3 That's why, I said most of the time
•  » » » » 2 years ago, # ^ |   +4 I like recursive dp!
•  » » 2 years ago, # ^ |   +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.
 » 2 years ago, # |   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.